[Python] 이것이 코딩테스트다 with 파이썬 - DFS/BFS - 미로 탈출

* 해당 문제 및 해설은 "이것이 코딩 테스트 다 with 파이썬" 책을 기준으로 요약 및 정리 하여 작성하였습니다.  

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

---

탐색 알고리즘 DFS / BFS ★★★★★

 

코딩테스트 단골 손님 탐색 알고리즘 DFS / BFS

스택과 큐, 재귀함수가 DFS / BFS 의 중요한 개념이기 때문에, 모르겠고 기초부터 해야한다면 글을 읽어보길 바란다.

 

DFS

DFS 는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이다.

 

• DFS 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.

 

BFS

BFS 는  Breath-First Search, 너비 우선 탐색이라고도 부르며, 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘 이다.

 

• DFS 는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다고 했는데 BFS는 그 반대다.
• BFS 구현에서는 선입선출 방식인 큐 자료구로를 이용하는 것이 정석이다.
• 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어,
  가까운 노드부터 탐색을 진행하게 된다.

---

 

문제 설명 : DFS / BFS - 미로 탈출

 

N X M 크기의 직사각형 형태의 미로에 갇혀 있다.
시작 위치는 (1, 1) 이고 미로의 출구는 (N, M) 의 위치에 존재하며 한 번에 한 칸 씩 이동할 수 있다.
탈출 하기 위해 움직여야 하는 최소 칸의 개수를 구하시오.
칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

입력 조건

 

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

 

출력 조건

 

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

 

예시

 

입력 예시	출력 예시
5 6 101010 111111 000001 111111 111111	10

 

답변 및 해설

 

이 문제는 BFS 로 해결할 수 있다.

예를 들어만약 미로의 크기가 3 X 3 이며 다음과 같이 되어있다고 가정해보자.

1 1 0
0 1 0
0 1 1

 

 단계 1  맨 처음에  ( 1 , 1 ) 의 위치에서 시작하며, ( 1 , 1 ) 의 값은 항상 1 이라고 문제에서 언급되어 있다.

 

  

 단계 2  ( 1 , 1 ) 좌표에서 상, 하, 좌, 우 로 탐색을 진행하면 바로 옆 노드인 ( 1 , 2 ) 위치의 노드를 방문하게 되고 새롭게 방문하는 ( 1 , 2 ) 노드의 값을 2 로 바뀌게 된다.

 

 

 

 단계 3  마찬가지로 BFS 를 계속 수행하면 결과적으로 다음과 같이 최단 경로의 값들이 1 씩 증가하는 형태로 변경된다.

 

 

소스 코드 

 

# N, M 을 공백으로 구분하여 입력받기

n, m = map(int,input().split());

# 2차원 리스트 맵 정보 받기

graph = []

for i in range(n) :
	graph.append(list(map(int,input())))

# DFS 로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문

def dfs(x, y):
  # 주어진 범위를 벗어나는 경우에는 즉시 종료
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False

  if graph[x][y] == 0 :
    # 해당 노드 방문 처리
    graph[x][y] = 1

    # 상, 하, 좌, 우 의 위치도 모두 재귀적으로 호출
    dfs(x - 1, y)
    dfs(x, y - 1)
    dfs(x + 1, y)
    dfs(x, y + 1)

    return True
  return False

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0

for i in range(n):
  for j in range(m):
    # 현재 위치에서 DFS 수행
    if dfs(i, j) == True:
      result += 1


print(result)

 

 

개인적인 생각

 

이번 문제의 경우에는, BFS 문제라고 바로 보일 수 있는 문제이다.
최적(최소) 의 경우를 찾는 경우에 생각하면서 구현을 하는게 좋을 것 같다.

이번 문제는 비교적 간단한 문제로, 보고 BFS 를 볼 수 있는 대표적인 문제이기 때문에 몇번이고 복습하는게 좋을 것 같다.

 

오늘의 개발자 명언

MS 가 Windows XP를 내어 놓자 모든 사람들은 이렇게 극찬했다.
“이제까지 가장 신뢰성이 높은 윈도우다 !”
하지만 나에게는 이렇게 말하는 것 같았다.
“아스파라거스가 이제까지 가장 확실한 채소다 !”
(Dave Barry, 컴퓨터광 유머 작가)

출처 : 프로그래밍에 관한 명언 101가지