본문 바로가기

BFS5

[python] 7562번 - 나이트의 이동 문제 파이썬 풀이 나이트의 이동을 좌표로 나타내면 다음과 같다. 따라서 이동 좌표들을 위와 같이 설정한 후 이동 반복문을 8번 반복하여 이동을 해준다. 그리고 이동할 때마다 이전 값에 +1한 값을 저장해준다. 그리고 목적지 좌표가 나오면 그 값에서 -1한 값을 리턴해준다(1부터 시작했으므로) 이동 좌표를 빼고는 이전 bfs들과 동일하다. from collections import deque import sys input = sys.stdin.readline t = int(input().rstrip()) def bfs() : dx = [-1, 1, 2, 2, 1, -1, -2, -2] dy = [2, 2, 1, -1, -2, -2, -1, 1] q = deque() q.append((startX, star.. 2021. 12. 13.
[python] 1697번 - 숨바꼭질 문제 파이썬 풀이 이동을 1칸씩 하던 이전과 달리 한칸과 2배 이동하는 순간이동이 추가되었다. 그래서 이동 변수를 함수 안에서 설정하고 [x-1, x+1, 2 * x]로 설정하여서 해당 위치에서 탐색을 진행하도록 하였다. 그리고 이동할 때마다 저장된 값을 1씩 증가하여 시간을 기록했다. 그리고 x의 값이 k와 같으면 x에 기록된 값을 리턴하도록 하였다. 1부터 시작했기때문에 마지막 출력에서는 1을 뺀 값을 출력하도록 하였다. 그런데 처음 작성한 코드에서 시간 초과가 나왔다. 시간초과가 나온 코드 from collections import deque import sys input = sys.stdin.readline n, k = map(int, input().rstrip().split()) q = dequ.. 2021. 12. 13.
[python] 7569번 - 토마토 문제 파이썬 풀이 해당 문제는 이전 문제인 7576토마토 문제가 3차원으로 변형된 문제이다. 2차원 탐색이였을 때 가졌던 이동 변수인 dx, dy에 dz를 추가하여 좌, 우, 앞, 뒤, 위, 6가지 이동을 할 수 있도록 해주면 될 것 같다. 3차원 탐색 BFS dx = [-1, 1, 0, 0, 0, 0] dy = [0, 0, -1, 1, 0, 0] dz = [0, 0, 0, 0, -1, 1] def bfs() : while q : x, y, z = q.popleft() for i in range(6) : nx = x + dx[i] ny = y + dy[i] nz = z + dz[i] if nx = n or ny = m or nz = h : con.. 2021. 12. 12.
[python] 7576번 - 토마토 문제 파이썬 풀이 최소 날짜를 구하기 위해서 BFS를 사용하고, 탐색을 할 때마다 이전 탐색 지점 + 1을 값으로 저장해주어 날짜를 저장해준다. 즉 마지막에 탐색하는 칸에는 가장 큰 값이 들어 있고, 1부터 시작했기 때문에 max값 -1 이 모두 익은 날짜 이다. 탐색을 어떤 식으로 시작을 해야할지에 고민이 많았는데 이 문제에서의 포인트는 미리 모든 토마토를 탐색하여 이미 익어있는 토마토를 탐색 큐에 집어넣고 탐색을 시작하는 것이 포인트였다. BFS 코드 def bfs() : while q : x, y = q.popleft() for i in range(4) : nx = x + dx[i] ny = y + dy[i] if nx = n or ny = m : contin.. 2021. 12. 12.

티스토리툴바