📖문제

동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력 조건

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

출력 조건

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

📝풀이과정

• 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하는 문제는 DFS보다 BFS로 푸는 것이 더 효율적이다.
• 다음 그래프에서 0번 노드에서 출발해서 9번 노드까지 가는 경우를 예로 들면
  
  
  DFS로 풀면 0번 노드에서부터 9번 노드까지로의 모든 경우를 확인한 후 움직인 칸의 개수를 비교한 후에야 답을 구할 수있다.
  하지만 BFS로 풀게되면 처음으로 9번 노드에 도착하는 경우가 최단경로임을 보장하기 때문에 모든 경우를 확인할 필요가 없다.

⌨코드

import sys
from collections import deque

# n, m 공백으로 구분하여 입력 받기
n, m = map(int, sys.stdin.readline().rstrip().split())

# 미로 정보 입력 받아서 리스트에 저장
graph = []
for _ in range(n):
  graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

# 방문 여부를 담는 이차원 리스트 초기화
visited = [[False] * m for _ in range(n)]

def bfs(graph, i, j, visited):

  # 우, 하, 상, 좌
  directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]

  # 큐 생성하고 시작 위치와 레벨 담기 (레벨: 이 위치까지 오는 데 방문한 최소 칸 개수)
  queue = deque()
  queue.append([0,0,1])

  while queue:
    cur = queue.popleft()
    visited[cur[0]][cur[1]] = True

    for direction in directions:
      next_row = cur[0] + direction[0]
      next_column = cur[1] + direction[1]

      # 다음 위치가 출구라면, (지금까지 들렀던 칸의 개수 + 1) 반환
      if next_row == n - 1 and next_column == m - 1:
        return cur[2] + 1

      # 다음 위치가 출구가 아니면,
      # 우선 다음 위치가 미로 맵을 벗어나지 않는지 확인
      if 0 <= next_row < n and 0 <= next_column < m:
        # 다음 위치가 아직 방문한 적이 없고, 괴물이 없는 부분인지 확인
        if not visited[next_row][next_column] and graph[next_row][next_column] == 1:
          queue.append([next_row, next_column, cur[2] + 1])

print(bfs(graph, 0, 0, visited))

💡 새로 알게된 점

파이썬에는 immutable 객체와 mutable 객체가 있다.

immutable 객체(불변 객체)

• bool, int, float, string, tuple이 불변 객체에 속한다.
• '=' 연산자를 사용하여 값을 변경할 때마다 새로운 객체를 생성한다.
• call by value 속성을 가지고 있다.

mutable 객체(가변 객체)

• list, dict, set이 가변 객체에 속한다.
• 인덱싱이나 슬라이싱으로 값을 변경할 수 있다.
  -> 함수 안에서 인덱싱이나 슬라이싱으로 값을 변경할 때 가변객체가 전역변수라면 global 키워드를 써주지 않아도 된다.
• call by reference 속성을 가지고 있다.

• 예시1 - (불변객체)

num = 1

def f():
  num = 2
  print(num) # 2


print(num) # 1
f()
print(num) # 1

• 예시2 - (가변객체)

num_list = [1, 3, 3, 4]

def f():
  num_list[1] = 2

print(num_list) #[1, 3, 3, 4]
f()
print(num_list) # [1, 2, 3, 4]