[DFS/BFS] ▲ 문제2 - 미로 탈출(152p)

[이코테] 문제2 - 미로 탈출(152p)

풀이 시간: 40~45분 이내

---

---

1) 문제 해결 아이디어

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다.

상하좌우로 연결된 모드 노드의 길이가 1로 동일하므로

(1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결 가능함

 

<책 코드와 다른 점>

1. 종료 조건 설정

항상 출구값을 리턴하기 때문에 종료 조건이 없어도 결과는 똑같다.

다만 종료 조건을 넣어주면 해당 좌표가 출구지점이 될 떄 까지만 탐색을 진행한다.

2. 탐색 조건에서 시작점 제외

상하좌우 탐색 시, 시작점은 갔던 곳이므로 탐색하지 않도록 조건을 설정하였다.

책의 코드처럼 시작점일 때도 탐색하게 해도 결과값은 달라지지 않지만 값이 3으로 덮어쓰여지게 된다.

 

<동작 과정>

1. 시작점에서 bfs() 호출

2. 큐에 시작점 삽입, 방문 처리(여기서 방문처리는 생략하였음)

3. 큐에서 1개 꺼내기 popleft()

4. 상하좌우 탐색

4-1. 가보지 않은 길이고 시작점이 아니면 큐에 삽임, 방문 처리(방문 처리할 칸의 값은 현재 지점 값에 1을 더한 값)

5. 3번에서 꺼낸 값이 출구지점이 될 때까지 4번 반복

 

첫번째 오류. 4-1번의 잘못된 방문 처리

처음에 전역변수(res)값을 두고 res값을 조정하여 값을 대입하여 방문처리를 하면 된다고 생각했지만

아래 코드처럼 방문 처리를 할 때는 현재 노드 값 기준으로 1을 더한 값으로 설정해야한다.

 

2) 소스코드

from collections import deque

n, m = map(int, input().split())  # 세로, 가로
# 0: 갈 수 없는 곳, 1: 갈 수 있는 곳
graph = [list(map(int, input())) for _ in range(n)]

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
  # 큐 구현을 위한 deque 라이브러리 사용
  queue = deque()
  queue.append((x, y))  # 현재 노드 삽입
  
  while queue:
    x, y = queue.popleft()  # 가장 오래된 노드 꺼내기
    
    # 종료 지점에 도착하면(종료 조건)
    if(x == n - 1 and y == m - 1):   
      return graph[n - 1][m - 1]  # 최소 이동 칸 개수 출력
    
    # 상하좌우 탐색
    for i in range(4):
      # 탐색할 인접 좌표
      nx = x + dx[i]
      ny = y + dy[i]

      # 좌표가 범위 내이면
      if(0 <= nx < n and 0 <= ny < m):
        # 갈 수 있는 곳이고 시작 위치가 아니라면
        if(graph[nx][ny] == 1 and [nx, ny] != [0, 0]):
          queue.append((nx, ny))  # 노드 삽입
          graph[nx][ny] = graph[x][y] + 1  # 방문처리

print(bfs(0, 0))  # 시작점 좌표에서 호출

 

<큐 구현 방법>

from collections import deque

queue = deque()	# 큐 생성
queue.append(2)	# 원소 삽입
queue.popleft()	# 제일 오래된 원소 반환/삭제

from collections import deque	큐 구현을 위한 deque 라이브러리 import
deque()
queue.append(원소)	원소 삽입
queue.popleft()	원소 삭제

 

<파이썬 에러 UnboundLocalError>

파이썬에서 전역 변수를 함수 내에서 사용하기 위해서 해당 함수 내에 global 키워드를 이용한다.

지역 범위에서 전역 변수를 사용할 수 있게 된다.

 

[참고] https://korbillgates.tistory.com/98

[파이썬] 파이썬 에러 UnboundLocalError: local variable referenced before assignment