[BOJ][Python] 2178번 - 미로탐색[DFS/BFS - 실버 1티어]

알고리즘 태그

[DFS/DFS 탐색]

태그 설명

BFS - 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
DFS - 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 해당 노드의 끝까지 탐색하고 목표 노드에 도달하면 멈추고 아니면 그 다음 노드의 자식노드들을 또 끝까지 탐색하는 방식의 탐색법

 

DFS, BFS 비교

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

문제

백준 문제 - 미로탐색

링크: 미로탐색

문제설명

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

예제 입력

4 6
101111
101010
101011
111011

예제 출력

15

예제 입력 2 

4 6
110110
110110
111111
111101

예제 출력 2 

9

 

DFS로는 최단거리를 찾을 수 없는거같다 이유인 즉슨 깊이탐색 알고리즘은 처음에 운이 좋게 찾으면 최단거리가 되지만 운이 안좋으면 모든 최장거리도 될 수 있으므로,,,? 모든 깊이를 탐색하고 성공 유무를 결정하기 때문에 최단거리 문제에는 어울리지 않는거같다 그래도 공부할겸 DFS/BFS 두 가지 방식으로 문제를 해결해보았다.

📃 소스코드 및 설명(DFS 실패)

from collections import deque
import sys
sys.setrecursionlimit(1000000)
N, M = map(int,input().split())

# N x M 방문 유무 확인 행렬 생성
visited = [[False] * M for _ in range(N)]

# N줄 만큼 입력
graph = [list(map(int, input().strip())) for _ in range(N)]

count = 1
def dfs(x, y):
  global count 
  if 0<=x<N and 0<=y<M:    
    #우리가 찾는 조건이 되면 count를 UP!
    if visited[x][y] == False and graph[x][y] == 1:
      visited[x][y] = True
      count += 1
      
      dfs(x+graph[x][y], y) # 오른쪽으로 이동
      dfs(x-graph[x][y], y) # 왼쪽으로 이동
      dfs(x, y+graph[x][y]) # 아래로으로 이동
      dfs(x, y-graph[x][y]) # 위로으로 이동
      
      # 타겟한 위치에 도착하면 리턴!
      if x == N - 1 and y == M-1:
        print(count)
        return

        
# 모든 행을 이동하면서 탐색할 필요가 없다 왜 why? 연결성을 확인할 필요 없이
# 이동할 수 있는 경우만 파악하면 된다. 
dfs(0,0)

📃 소스코드 및 설명(BFS 성공)

from collections import deque
N, M = map(int,input().split())

# N x M 방문 유무 확인 행렬 생성
visited = [[False] * M for _ in range(N)]

# N줄 만큼 입력
graph = [list(map(int, input().strip())) for _ in range(N)]

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

def bfs(x, y):
  queue = deque()
  queue.append([x, y])  
  
  while queue:
    x, y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      
      # 끔점이 나오면 끝내주고, 마지막에 누적된 합을 print
      if x == N -1 and y == M-1:
        print(graph[N -1][M-1])
        break
        
      if 0<=nx<N and 0<=ny<M:      
        if visited[nx][ny] == False and graph[nx][ny] == 1:
	      # 이동할 자리에 현재 누적된 값 + 1을 해주면서 누적해 나간다.          
          graph[nx][ny] = graph[x][y] + 1
          visited[nx][ny] = True
          queue.append([nx, ny])
          
        
bfs(0,0)