[BOJ] 2178번 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

1 . DFS를 이용한 풀이

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
maze = []

for _ in range(n):
    maze.append(list(map(int, list(sys.stdin.readline().rstrip('\n')))))

    
def isSafe(maze, x, y, mark):
    if x<0 or x>=m or y<0 or y>=n:
        return False
    
    if maze[y][x] == 0 or mark[y][x] == 1:
        return False
    
    return True


def solve(maze, x, y, mark):
    deq = deque()
    cnt = 0
    
    mark[y][x] = 1
    deq.append((x, y))
    deq.append((None, None))
    
    while deq:
        i, j = deq.popleft()
        
        if i == None:
            cnt += 1
            deq.append((None, None))
            continue

        
        if i == m-1 and j == n-1:
            return cnt+1
        
        if isSafe(maze, i+1, j, mark):
            deq.append((i+1, j))
            mark[j][i+1] = 1
        
        if isSafe(maze, i-1, j, mark):
            deq.append((i-1, j))
            mark[j][i-1] = 1
            
        if isSafe(maze, i, j+1, mark):
            deq.append((i, j+1))
            mark[j+1][i] = 1
            
        if isSafe(maze, i, j-1, mark):
            deq.append((i, j-1))
            mark[j-1][i] = 1
        
mark = [[0 for _ in range(m)] for _ in range(n)]
res = solve(maze, 0, 0, mark)
print(res)

 

2. BFS를 이용한 풀이

from collections import deque

n, m = map(int, input().split())
arr = []
for _ in range(n):
    data = list(map(int, list(input())))
    arr.append(data)
    
    
x, y = 0, 0
q = deque()
q.append((x, y))


dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while q:
    x, y = q.popleft()
    
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        
        if not(0<=nx<n and 0<=ny<m):
            continue
            
        if arr[nx][ny] == 1:
            arr[nx][ny] = arr[x][y] + 1
            q.append((nx, ny))

print(arr[n-1][m-1])

 

흔한 유형의 문제다.

DFS보다는 BFS가 더 간결해 보인다. 

다양한 방법으로 풀어보는게 좋을 것 같다.