본문 바로가기

Algorithm Problems/그래프

 (50)
[백준/Python] 2178번: 미로 탐색 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 요약 N × M 크기의 미로에서 (1, 1)에서 출발하여 (N, M) 위치로 이동할 때 지나야 하는 최소 칸 수를 출력한다. + 서로 인접한 칸으로만 이동할 수 있다. + 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타낸다. + 칸을 셀 때, 시작 위치와 도착 위치도 포함한다. 코드 from collections import deque # BFS 탐색 def bfs(): que.append((0, 0)) c..
[백준/Python] 17471번: 게리맨더링 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 요약 1번부터 N번까지 N개의 구역으로 나누어진 지역을 두 개의 선거구로 나눈다, + 선거구는 구역을 적어도 하나 포함해야 한다. + 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. (구역 A에서 구역 B로 갈 수 있을 때, 두 구역이 연결되어 있다고 한다.) 공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이의 최솟값을 출력한다. 코드 from itertools import com..
[백준/Python] 1697번: 숨바꼭질 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 요약 수빈이의 위치가 N이고, 동생의 위치가 K일 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 출력한다. 수빈이는 걷거나 순간이동을 할 수 있다. 수빈의 위치가 X일 때 걷는다면 1초 후에 N-1 또는 N+1로 이동하고, 순간이동을 하는 경우에는 1초 후에 2 × N 위치로 이동하게 된다. 코드 def bfs(): que = deque(..
[백준/Python] 11060번: 점프 점프 문제 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 요약 재환이는 n개의 칸으로 이루어진 미로의 가장 왼쪽 끝 칸에 존재한다. 칸에 쓰여져 있는 수만큼 오른쪽으로 떨어진 칸으로 이동할 수 있을 때, 가장 오른쪽 끝 칸으로 이동할 수 있는 최소 점프 횟수를 출력한다. 가장 오른쪽 끝 칸으로 이동할 수 없는 경우 -1을 출력한다. 코드 from collections import deque def min_jump(arr): n = ..
[백준/Python] 2606번: 바이러스 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 문제 요약 n개의 컴퓨터가 m개의 네트워크로 연결되어 있을 때, 1번 컴퓨터가 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 바이러스에 감염되는 컴퓨터 수를 출력한다. 두 컴퓨터가 네트워크로 연결되어 있을 때, 하나의 컴퓨터가 바이러스에 감염되면 다른 컴퓨터도 바이러스에 감염된다. 코드 def dfs(start): global cnt check[start] = 1 for i in tree[start]..
[Python/백준] 5639번: 이진 검색 트리 문제 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 요약 이진 검색 트리를 전위 순회(루트-왼쪽-오른쪽)한 결과가 주어졌을 때, 그 트리를 후위 순회(왼쪽-오른쪽-루트)한 결과를 출력한다. 이진 검색 트리란 세 가지 조건을 만족하는 이진 트리이다. 조건 1. 노드의 왼쪽 서브트리에 있는 모든 노드의 key는 노드의 key보다 작다. 조건 2. 노드의 오른쪽 서브트리에 있는 모든 노드의 key는 노드의 key보다 크다. 조건 ..

티스토리툴바