[이.취.코] Chap 5. BFS - 미로 탈출

@mildsalmon·2021-08-17 05:24

1. 미로 탈출

난이도
- 중하
풀이 시간
- 30분
시간 제한
- 1초
메모리 제한
- 128MB

A. 문제

N*M 크기의 직사각형 형태의 미로가 있다. 초기 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재한다. 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 이때 미로를 탈출하기 위한 최소 칸의 개수를 구하시오.

a. 입력 조건

첫째 줄에는 두 정수 N, M이 주어진다.
- 4 <= N, M <= 200
N개의 줄에는 각각 M개의 정수(0 또는 1)로 미로의 정보가 주어진다.
- 각각의 수들은 공백 없이 붙어서 제시된다.
- 시작 칸과 마지막 칸은 항상 1이다.

b. 출력 조건

첫째 줄에 최소 이동 칸의 개수를 출력한다.

c. 테스트 케이스

입력 예시

출력 예시
```
10
```

B. 내 답안

a. 첫 시도 - 틀림


from collections import deque  
  
# n, m = list(map(int, input().split()))  
miro_map = []  
miro_map_2 = []  
  
n, m = [5, 6]  
v = ['101010',  
     '111111',  
     '000001',  
     '111111',  
     '111111']  
  
for i in range(n):  
    a = list(map(int, v[i]))  
    miro_map.append(a[:])  
    miro_map_2.append(a[:])  
  
  
start_point = [0, 0]  
end_point = [n-1, m-1]  
  
moves = deque()  
moves.append(start_point)  
  
d = ((0, -1), (1, 0), (0, 1), (-1, 0))  
result = 0  
  
while moves:  
    # count = count + 1  
    print("moves :", moves)  
    move = moves.popleft()  
    print(move)  
    count = 0  
    x = move[0]  
    y = move[1]  
    result = result + 1  
    miro_map_2[x][y] = 0  
  
    print(*miro_map, sep='\n')  
    print("miro_2\n", *miro_map_2, sep='\n')  
  
    for j in range(4):  
        dx = x + d[j][0]  
        dy = y + d[j][1]  
        if dx >= 0 and dx < n and dy >= 0 and dy < m:  
            if miro_map_2[dx][dy] == 1:  
                count = count + 1  
                moves.append([dx, dy])  
                miro_map[x][y] = result  
  
            # else:  
    if count < 1:  
        result = result - 1  
    print("result :", result)  
  
print(result)

b. 두 번째 시도 - 성공


from collections import deque  
  
# n, m = list(map(int, input().split()))  
miro = []  
miro_2 = []  
n, m = [5, 6]  
v = ['101010',  
    '111111',  
    '000001',  
    '111111',  
    '111111']  
  
for i in range(n):  
    a = list(map(int, v[i]))  
    miro.append(a[:])  
    miro_2.append(a[:])  
  
roots = deque()  
roots.append([0, 0])  
  
d = [(0, -1), (1, 0), (0, 1), (-1, 0)]  
  
while roots:  
    x, y = roots.popleft()  
    miro_2[x][y] = 0  
    count = 0  
  
 for j in range(4):  
        dx = x + d[j][0]  
        dy = y + d[j][1]  
  
        if dx < 0 or dx >= n or dy < 0 or dy >= m:  
            continue  
  
        if miro[dx][dy] == 0:  
            continue  
  
        if miro[dx][dy] == 1 and miro_2[dx][dy] != 0:  
            roots.append([dx, dy])  
            miro[dx][dy] = miro[x][y] + 1  
            count = count + 1  
        elif miro[dx][dy] >= 1:  
            count = count + 1  
    if count <= 1:  
        if x == 0 and y == 0:  
            miro[x][y] = 1  
        else:  
            miro[x][y] = 0  
  
    print(x,y)  
    print(*miro, sep='\n')  
    print()  
    print(*miro_2, sep='\n')  
  
    if miro[n-1][m-1] != 1:  
        break  
  
print(miro[n-1][m-1])  
  
###########################################  
############ 결과 값 #######################
# 10  
#  
# map  
# [1, 0, 0, 0, 0, 0]  
# [2, 3, 4, 5, 6, 7]  
# [0, 0, 0, 0, 0, 8]  
# [1, 1, 1, 1, 10, 9]  
# [1, 1, 1, 1, 1, 10]

a. 회고

반성

이번에도 첫 시도는 1시간 30분 정도 걸리고 구현에도 실패했다.

두번째 시도를 통해 답지도 나랑 비슷한 방식으로 진행하되, miro[dx][dy] == 1일때 miro[dx][dy] = miro[x][y] + 1을 했다. 나는 miro[dx][dy] == 1일때 miro[x][y] = result를 했다. 답지는 현재 좌표 한칸 앞을 바꾼 것이고 나는 현재 좌표를 바꿨다. 그래서 원하는 답이 안나온 것이다. 그리고 답지보다 속도(효율)을 향상시켜봤다. 답지는 모든 칸(1이 입력된 칸)을 수정하기 전까지 동작을 멈추지 않는다. 하지만 나는 원하는 길(n,m)까지 가는 최단 경로를 찾으면 loop를 탈출하도록 하여 성능을 향상시켰다.

결론

뭘 써야하는지는 대충 알겠다. (다만, 이 부분은 문제를 더 많이 풀어봐야 확실할 것 같다.) 그런데 어떤 방식으로 풀어나가야 하는지(구현해야 하는지) 잘 모르겠다. 이 부분은 전체적인 개념이 끝나고 비슷한 문제 100문제 정도 풀면 알아지겠지.

난 신은 아니지만, 이 정도는 가뿐히 성취할 수 있다고 믿는다. 그리고 이를 실현시킬 수 있는 습관도 쉽게 만들 수 있다고 믿는다.

C. 문제 해설

BFS를 이용했을 때 매우 효과적으로 해결할 수 있다. BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다. (1, 1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.