[Problem Solving] 음료수 얼려 먹기

DFS & BFS

이번에는 DFS와 BFS의 개념을 활용해 풀어야 하는 문제인 "음료수 얼려 먹기" 알고리즘 문제를 풀어보겠습니다.

 

문제 : N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총아이스크림의 개수를 구하는 프로그램을 작성하시오.

 

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

 

얼음틀

구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1이므로 위의 얼음틀 예시에서는 총 3개의 아이스크림이 생성된다. 이 문제는 DFS를 통해 '0'인 값이 상, 하, 좌, 우로 연결되어 있는 노드를 묶어 구할 수 있다.

 

입력 예시	출력 예시
15 14 00000111100000 11111101111110 11011101111110 11011101100000 11011111111111 11011111111100 11000000011111 01111111111111 00000000011111 01111111111000 00011111111000 00000001111000 11111111110011 11100011111111 11100011111111	8

 

# 얼음 틀의 세로 길이와 가로길이를 입력 받음.
n, m = map(int, input().split())

# 얼음 틀을 저장할 2차원 리스트
graph = []

for i in range(n):
	graph.append(list(map(int, input())))
 
 
# N, M 즉 얼음 틀의 좌표 값을 인자로 받음.
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):
		if dfs(i, j) == True:
			result += 1
            
print(result)          

 

이번에 공부한 "음료수 얼려 먹기" 문제는 DFS 개념에 활용이었던 것 같다. 처음 볼 때에는 그냥 DFS 개념에 방향벡터만 쓰면 될 줄 알았는데 상, 하, 좌, 우 모두 재귀적으로 함수를 호출해서 탐색을 해야 했다. 그래서 이해하는데 조금 시간이 걸렸지만 이해하고 나니 괜찮은 것 같다.