[백준 2178] 미로 탐색

1. 문제

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

2178번: 미로 탐색

2. 접근 방법

미로 == bfs 아니겠습니까

 

근데 이 문제에서 주의할 점이 하나있는데,

입력 받을 때 입력 값이 빈 칸이 기준이 아니라 그냥 숫자 하나씩이어서 input할 때 split()은 사용안해두 됩니당

 

1. board의 영역을 벗어나는지 확인하는 함수 (is_road)

2. bfs 함수

사실 문제에서 무조건 도착하는 입력 값만 주어진다고 해서,

visit 체크하기 귀찮아서 그냥 지나간 자리는 값을 0으로 바꾸어주면서 cnt를 같이 넘겨줬습니다.

 

지금 보니까 지나간 자리에 cnt를 넣어주고 (M-1, N-1)자리에 도착하면 return해주고 board[M-1][N-1]값을 프린트해도 됐을거같아여

3. 코드

python

from collections import deque

def is_road(x, y):
    global N, M
    if 0 <= x < M and 0 <= y < N:
        return True
    return False


def find_exit(ix, iy, i_cnt):
    global board
    q = deque()
    q.append((ix, iy, i_cnt))

    _dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while q:
        x, y, cnt = q.popleft()
        if (x, y) == (M-1, N-1):
            return cnt
        for i in range(4):
            _x, _y = x + _dir[i][0], y + _dir[i][1]
            if is_road(_x, _y) and board[_y][_x] == 1:
                q.append((_x, _y, cnt+1))
                board[_y][_x] = 0


N, M = map(int, input().split())
board = [list(map(int, input())) for _ in range(N)]
print(find_exit(0, 0, 1))

4. 마치며

dfs, bfs를 끝장내겠슴다