[DFS][BFS][Python]미로탈출과 미로의 거리

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

class position(): def __init__(self, x, y, dist): self.x = x self.y = y self.dist = dist def dfs(x, y, dist=1): global result visit[y][x] = True # print((x, y)) if (x, y) == end: result = 1 for i in range(len(direction)): next_y = y + direction[i][0] next_x = x + direction[i][1] if next_y >= 0 and next_y < n and next_x >= 0 and next_x < n: if maze[next_y][next_x] == 0 and visit[next_y][next_x] == False or maze[next_y][next_x] == 3: dfs(next_x, next_y) def bfs(x, y, dist): global result queue.append(position(x, y, dist)) visit[y][x] = True while queue: current = queue.pop(0) if current.x == end[0] and current.y == end[1]: result = current.dist-2 break for i in range(4): next_y = current.y + direction[i][0] next_x = current.x + direction[i][1] next_dist = current.dist + 1 if next_x >= 0 and next_y >= 0 and next_x < width and next_y < height: if visit[next_y][next_x] == False and maze[next_y][next_x] == 0 or visit[next_y][next_x] == False and maze[next_y][next_x] == 3: visit[next_y][next_x] = True queue.append(position(next_x, next_y, next_dist)) direction = ((1, 0), (-1, 0), (0, 1), (0, -1)) for t in range(int(input())): n = int(input()) width = height = n visit = [[False] * n for _ in range(n)] # visit = [[False] * n] * n 로 하면 안됨! queue = [] result = 0 maze = [list(map(int, input())) for _ in range(n)] for i in range(height): for j in range(width): if maze[i][j] == 3: end = (j, i) if maze[i][j] == 2: start = (j, i) # bfs(start[0], start[1], 1) dfs(start[0], start[1]) print("#{} {}".format(t+1, result))

4875. [파이썬 S/W 문제해결 기본] 5일차 - 미로
5105. [파이썬 S/W 문제해결 기본] 6일차 - 미로의 거리