[BOJ] 백준 2178. 미로탐색

🥈 미로 탐색

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

192 MB

181911

82006

52295

43.640%

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1

1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

💡 아이디어

문제보자마자 BFS로 그냥 풀어보자 싶었다.

심지어 항상 도착위치로 이동할 수 있는 경우만 주어져서 고려할 것이 많이 없는 것 같았다.

1. 입력을 명확하게 받는다 → 개인적으로 제일 어려워하는 부분임..
2. BFS로 구현해준다 ( 0은 이동불가, 1이면서 방문하지 않은 칸을 이동한다 )
3. 단, 다음으로 가는 칸은 현재 칸의 값을 더해준다 ( + 1 씩 쭉쭉더해준다)
4. 맨 마지막 칸의 값을 출력해준다

📝 풀이

from collections import deque

n, m = map(int, input().split())

miro = [list(map(int, input())) for i in range(n)]
visited = [[False for i in range(m)] for i in range(n)]

q = deque()
q.append((0, 0)) #가장 첫번째 index 넣어준다

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]

while q:
    y, x = q.popleft()
    visited[y][x] = True #방문처리를 해준다
    for i in range(4): #위아래좌우 탐색해준다
        ny = y + dy[i]
        nx = x + dx[i]
        #다음꺼가 1이고 nx, ny이 범위내에 있고, 방문하지 않았따면?
        if 0 <= ny < n and 0 <= nx < m:
            if miro[ny][nx] == 1 and visited[ny][nx] == False:
                q.append((ny, nx))
                miro[ny][nx] += miro[y][x]

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

👩🏻‍💻

사실 너무 기본적인 유형의 문제라

금방 떠올리고 코드를 짰으나 n*m과 x,y가 너무 헷갈려서 오래걸렸다.

그려가면서 푸는게 제일 실수 없이 빨리 푸는듯하다. ㅜㅜ