BFS3 [백준] 1697: 숨바꼭질 python 구현 / BFS 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 풀이 n과 k의 범위를 제한하여 음수 or 큰 수에 대한 필요 없는 탐색은 진행하지 않을 것 n==k 일 경우를 대비할 것 vst를 사용하여 한 번 탐색한 곳은 다시 탐색하지 않을 것 CODE from collections .. 2023. 3. 20. [백준] 2178: 미로 탐색 python 구현 / BFS 문제 N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 아래와 같은 예시 일 경우 최소경로를 출력해야 한다. CODE import sys from collections import deque n, m = map(int, input().split()) maze = [[int(i) for i in.. 2023. 3. 20. [백준] 1260: DFS와 BFS, python 구현 1. 입력 코드 구현 해당 코드에서 인접 리스트가 정렬되어야 작은 수를 우선으로 탐색한다. DAT(Direct Access Table)를 위한 visited 변수를 만듦 node, edge, st_node = map(int, input().split()) adj_list = [[] for _ in range(node+1)] for _ in range(edge): i, j = map(int, input().split()) adj_list[i].append(j) adj_list[j].append(i) adj_list = [sorted(i) for i in adj_list] visited = [0]*(node+1) 2. DFS 구현 dfs는 깊이 우선 탐색이기 때문에 stack으로 구현한다. 노드를 받기위한 .. 2023. 2. 20. 이전 1 다음
