[백준] 2178번(미로 탐색)

백준 2178번

처음 제출한 코드(시간초과)

import sys
input = sys.stdin.readline

# 값 입력 받기
n, m = map(int, input().split())
array = [input().rstrip() for _ in range(n)]

# 가장 짧은 길의 거리를 저장하기 위한 변수 선언
shortest_path = n*m

# 재귀함수호출의 한계를 n*m으로 설정
# 가장 짧은 길의 거리는 모든 노드를 거친 값보다 클 수 없음
sys.setrecursionlimit(n*m)

# 방문한 노드를 체크하기 위한 리스트
visited = [[False for _ in range(m)] for _ in range(n)]

# 깊이 우선 탐색 함수
def solution(row, col, depth):

  global shortest_path

  # 현재 경로의 depth가 shortest_path에 저장된 값보다 커지면 return
  if depth > shortest_path: return
  # row, col 값이 인덱스 범위를 벗어나면 return
  if row<0 or row>=n or col<0 or col>=m: return
  # 탐색하고자 하는 곳이 진입 불가능한 곳(0)이면 return
  if array[row][col] == "0": return
  # 이미 방문했던 곳이면 return
  if visited[row][col] == True: return
  
  # array[n][m]에 도착하면 현재 경로의 depth를 shortest_path와 비교하여 더 값은 값을 저장
  if row==n-1 and col==m-1:
    shortest_path = min(depth, shortest_path)
    return

  # 현재 노드 방문 처리
  visited[row][col] = True
  
  # 갈 수 있는 모든 경로에 대해 재귀함수호출
  solution(row+1, col, depth+1)
  solution(row, col+1, depth+1)
  solution(row-1, col, depth+1)
  solution(row, col-1, depth+1)
  
  # 현재 호출된 함수가 끝나면 다시 노드를 비방문 처리
  visited[row][col] = False

solution(0,0,1)
print(shortest_path)

.

◼️ 깊이 우선 탐색(DFS)를 활용한 문제 풀이

• 계속해서 시간초과로 인한 오답
  ⇒ 실행시간을 줄이기 위해 여러 조건문을 추가했으나 여전히 시간초과

• WHY❓
  ▪️ 이 문제는 목적 노드까지 가는 가장 짧은 경로를 탐색하는 문제
  ▪️ 깊이 우선 탐색에서는 목적지에 도달했다고 한들 이 경로가 최적인지 판단할 수가 없음
  ⇒ 아직 탐색하지 않은 다른 경로가 더 짧을 수 있기 때문에!
  ▪️ 결국 모든 경로를 탐색할 수 밖에 없음

• 하지만 넓이 우선 탐색(BFS)에서는
  ▪️ level별로 탐색을 하기 때문에 만약 목적 노드에 도착했다면 그것이 최적 경로
  ▪️ 아직 가지 않은 경로에 대해 그 깊이를 알 수는 없지만, 우리가 알고 싶은 것은 최소 길이이기 때문에 고려할 필요 없음
  ⇒ 최적 경로를 찾기 위해 모든 경로를 탐색해야 하는 DFS보다 훨씬 효율적

⇒ 넓이 우선 탐색(BFS)으로 전환하여 문제 풀이

.

최종 제출 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
array = []
for i in range(n):
  array.append(list(map(int, input().rstrip())))

# 넓이 우선 탐색에 사용할 queue 리스트 생성
queue = [[0,0]]
# 다음 경로 탐색을 위한 x,y 인덱스 값 변경 리스트
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def solution(x, y):

  # 현재 위치에서 갈 수 있는 모든 경로에 대해
  for i in range(len(dx)):
    # 해당 노드가 존재하는지 판별하고, 없으면 continue
    if x+dx[i] <0 or x+dx[i] >= m or y+dy[i] <0 or y+dy[i] >= n:
      continue
      
    # 이동하려는 노드가 이동 가능한 곳인지 판별 & 방문한 적 없는 곳인지 판별
    # 이동 가능한 곳이면 시작점에서 노드까지의 거리를 업데이트하고 queue에 해당 노드를 집어넣는다
    # (방금 탐색한 노드의 자식 노드들을 탐색하기 위함)
    if array[y+dy[i]][x+dx[i]] == 1:
      array[y+dy[i]][x+dx[i]] = array[y][x]+1
      queue.append([x+dx[i],y+dy[i]])

# 그래프를 넓이 우선으로 탐색
while queue:
  element = queue.pop(0)
  solution(element[0], element[1])

# 결과값 출력
print(array[n-1][m-1])

.

◼️ 넓이 우선 탐색 방식으로 문제 풀이

• 기본적인 논리는 넓이 우선 탐색 함수와 동일
• 현재 탐색 중인 노드를 queue에 추가할지 말지만 검사해주면 됨
  ▪️ 이동 가능한 방향에 노드가 존재하는지 확인
  > if x+dx[i] <0 or x+dx[i] >= m or y+dy[i] <0 or y+dy[i] >= n:
  ▪️ 존재하는 노드가 이동 가능한 노드(array[x][y]값이 1)이며, 방문한 적 없는 노드(array[x][y]값이 업데이트 안 됨)인지 확인
  > if array[y+dy[i]][x+dx[i]] == 1
• 탐색이 종료되면 array[n][m]에 저장된 값인 목적 노드까지의 최적 경로 길이를 출력