[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 크기의 얼음 틀이 있다.
구멍이 뚫려 있는 부분은 0, 칸만이가 존재하는 부분은 1로 표시 된다.
이 때 얼음 틀의 모양이 주어졌을 때, 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
다음 4 X 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

 

그림 예시

 

0 0 1 1 0
0 0 0 1 1
1 1 1 1 1
0 0 0 0 0  

0	0	1	1	0
0	0	0	1	1
1	1	1	1	1
0	0	0	0	0

 

입력 조건

 

• 첫번째 줄에 얼음 틀의 세로 길이 N 과 가로 길이 M 이 주어진다. ( 1 ≤ N, M ≤ 1,000)
• 두번째 줄 부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이 때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1 이다.

 

출력 조건

 

• 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

 

예시

 

입력 예시

출력 예시

15 14 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1  1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1  0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1

8

  

답변 및 해설

 

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

 

1.  특정한 지점의 주변 상, 하, 좌, 우 를 살펴본 뒤에 주변 지점 중에서 값이 '0' 이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점에서 다시 상, 하, 좌, 우 를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
3. 1 ~ 2 번 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

 

# 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)

 

개인적인 생각

 

DFS / BFS 문제는 꼭 다시 한번 씩 풀어봤으면 좋겠다.

위의 풀이는 책에 나온 것을 보고 작성하였으나, 더 간단하게 풀 수 있지 않을까 싶다.
맨 처음 문제를 접했을 때, 재귀함수가 생각났고 그에 따라 DFS 로 푸는 방식을 생각하면 된다.

상, 하, 좌, 우 라는 그리디 알고리즘 문제를 봤다면 그거에 따른, 재귀함수를 호출해야겠다 라고 생각했다면
지금 이 책 또는 블로그를 굉장히 잘 보고 있다고 생각합니다.

 

오늘의 개발자 명언

젠장. 이젠 밖에 있는 모든  운영 시스템이 똑같아졌다.
(2003년 MS 부사장, 브라이언 발렌타인이 OS 보안을 이야기하며)

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