[백준/파이썬] 2178번<미로 탐색> 문제 풀이

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

2178번: 미로 탐색

문제

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

예제 입력 1 복사

4 6
101111
101010
101011
111011

예제 출력 1 복사

15

예제 입력 2 복사

4 6
110110
110110
111111
111101

예제 출력 2 복사

9

예제 입력 3 복사

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3 복사

38

 

 

---

사고 흐름

미로 문제 싫다..ㅎ 

-> 이동한 최소 칸(이동거리)을 구하는 문제는 bfs로 풀 수 있다

-> 큐를 이용해 bfs로 풀어야겠다!

-> 출발점과 인접한 점들의 좌표를 가져와야하는데 함수 adj를 작성해 조금 무식한 방법으로 인접한 점들 좌표를 구했다

-> while문 안에서 큐 맨 앞 원소를 pop해서 그 원소와 인접한 좌표들에 대해 큐에 추가하고 방문 표시를 한다

-> 근데 이동 거리는 어떻게 구하지?.. (막혔던 부분)

-> cnt라는 이차원 배열을 놓고 해당 점에 인접한 점들의 cnt를 똑같이 +1 해준다. 나에겐 이 부분이 중요했던 것 같다

 

문제 핵심과 알고리즘

최소거리를 구하는 문제는 bfs로 푼다! 그리고 효율적으로 점에 인접한 좌표들 구하기

def bfs(v) :
    queue=[v]
    discovered=[v]
    cnt=[[1 for _ in range(m)] for _ in range(n)]

    while True :
        if cnt[n-1][m-1]!=1 :
            return cnt[n-1][m-1]
        now = queue.pop(0)
        adj_list=adj(now)
        for a in adj_list :
            if miro[a[0]][a[1]] == 1 and a not in discovered:
                queue.append(a)
                discovered.append(a)
                cnt[a[0]][a[1]]=cnt[now[0]][now[1]]+1

def adj(v) :
    adj_list=[(v[0]-1, v[1]), (v[0], v[1]-1),(v[0]+1, v[1]),(v[0], v[1]+1)]

    if (v[0]-1)==-1 :
        adj_list.remove((v[0]-1, v[1]))
    if (v[1]-1)==-1 :
        adj_list.remove((v[0], v[1]-1))
    if (v[0]+1)==n :
        adj_list.remove((v[0]+1, v[1]))
    if (v[1]+1)==m :
        adj_list.remove((v[0], v[1]+1))

    return adj_list

n, m = map(int, input().split())
miro=[list(map(int, input())) for i in range(n)]
v=(0,0)
print(bfs(v))

 

문제 풀면서 헤맸던 부분

1. 이동 거리 구하기

  원래는 cnt라는 변수에서 +1 하면서 이동거리를 구했는데, 도저히 그럴 수 없어서,, 고민하다가 결국 구글링으로 해결했다. cnt라는 이차원 배열을 만들어 원래 점에서 인접한 점들에 해당하는 좌표에 +1 해준다. 그리고 인접한 점들 중 하나로 이동하고 그 점의 인접한 점들에 대해서도 +1한다. 그래프 모양으로 생각하면 쉬운 개념이지만 카운트를 위한 리스트를 하나 더 만들어 카운트할 생각은 못했다.

 => 그래프의 깊이(이동거리)를 카운트하기 위한 리스트가 있다는 걸 잊지말자!

 

다른 사람 풀이 참고해 배운 점

from collections import deque

n, m = map(int, input().split())
maze = []

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

for i in range(n):
    maze.append(list(map(int, input())))

queue = deque([(0,0)])

while queue:
    x, y = queue.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if maze[nx][ny] == 1:
                queue.append([nx, ny])
                maze[nx][ny] = maze[x][y] + 1

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

여기서는 dx, dy로 좌표 이동을 간단하게 나타냈고(이런 형식은 기억하는게 좋을 것 같다), 해당 점에 인접한 점들에 대해 범위에 존재하고 1이면 큐에 추가하는 방식으로 진행했다. 나는 인접한 점들을 리스트로 만든 후 그 리스트를 돌면서 확인을 했지만 여기서는 만들면서 확인을 하고 있다.