백준 5105번 파이썬 문제풀이(미로의 거리) - BFS, DFS

간단한 BFS 구현이다. Visited 리스트를 따로 만들어 해당 위치에서 도착지까지 얼마나 걸리는지 계속해서 확인해면서 가도록 구현했다. 단 DFS의 다양한 방법으로도 구현해 보았다. 모든 코드를 제시 하겠다.

 

1.BFS

import sys
from collections import deque

sys.stdin = open('input.txt', 'r')


def bfs(start):
    queue = deque([start])
    visited = [[0] * N for _ in range(N)]
    visited[start[0]][start[1]] = 1

    dr = [-1, 0, 1, 0]  # 상우하좌
    dc = [0, 1, 0, -1]  # 상우하좌
    while queue:
        r, c = queue.popleft()

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]

            if nc < 0 or nc >= N or nr < 0 or nr >= N or array[nr][nc] == 1:
                continue

            if array[nr][nc] == 3:
                visited[nr][nc] = visited[r][c] + 1
                print(visited)
                return visited[nr][nc] - 2

            elif not visited[nr][nc]:
                visited[nr][nc] = (visited[r][c] + 1)
                queue.append((nr, nc))
    return 0


T = int(input())

for order in range(1, T + 1):
    N = int(input())
    array = []
    start = (-1, -1)
    for i in range(N):
        temp = list(map(int, input()))
        for j in range(len(temp)):
            if temp[j] == 2:
                start = (i, j)
                break
        array.append(temp)

    print(f'#{order} {bfs(start)}')

 

2. DFS

import sys

sys.stdin = open('input.txt', 'r')


def dfs(r, c, count):
    global min_
	
    if r < 0 or r >= N or c < 0 or c >= N or array[r][c] == 1:
        return
	#가지치기
    if count > min_: #만약 횟수가 이미 저장된 최솟값보다 크다면 리턴
    	return
	#기저
    if array[r][c] == 3:
        if min_ > count:
            min_ = count
        return
    else:
        array[r][c] = 1
        

	#재귀
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]

        dfs(nr, nc, count + 1)

     array[r][c] = 0

T = int(input())
dr = [-1, 0, 1, 0]  # 상우하좌
dc = [0, 1, 0, -1]  # 상우하좌

for order in range(1, T + 1):
    N = int(input())
    array = []
    start = (-1, -1)
    min_ = 1 << 20
    for i in range(N):
        temp = list(map(int, input()))
        for j in range(len(temp)):
            if temp[j] == 2:
                start = (i, j)
                break
        array.append(temp)
    dfs(start[0], start[1], 1)
    if min_ >= 1 << 20:
        min_ = 2
    print(f'#{order} {min_ - 2}')