[Python][이코테] 음료수 얼려 먹기

배경

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.

구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.

이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오

 

4 5
00110
00011
11111
00000

답)

3

 

입력 조건

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

출력 조건

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

 

문제 해설

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

 

2022.08.01 - [Algorithm/이것이 코딩테스트다] - [Python][이코테] DFS

[Python][이코테] DFS

 

 

동작 순서는

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

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

graph = []

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

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-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    
    return False
        

for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1
            
print(result)

 

 

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

 

코드를 보면서 설명을 하자면

 

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-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    
    return False
    
    
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1
            
print(result)

우선 (0, 0)부터 시작한다.

 

(0, 0) 이 0 이기 때문에 해당 지점을 방문했다는 표시로 1로 표기 후

 

재귀를 이용하여 (1, 0)으로 이동한다.

 

(1, 0) 지점 또한 0 이기 때문에 다시 또 dfs(x+1, y)로 이동하여 

 

(2, 0) 지점으로 이동한다.

 

(2, 0)은 1이기 때문에 if문을 건너 띄고 return False로 이전 (1, 0)을 수행했던 지점으로 돌아간다.

 

(1, 0) 다음 지점은  dfs(x-1, y)이고 (0, 0)은 1이기 때문에 다시 (1, 0)을 수행했던 지점으로 돌아간다.

 

그다음 순서는 dfs(x, y+1)로 (1, 1) 지점은 0으로 1로 바꿔주고 다시 dfs(x+1, y)를 수행한다.

 

(2, 1)은 1로 (1, 1)로 돌아가고 dfs(x-1, y)는 (0, 1)로 1이기 때문에 다시 dfs(x+1, y)를 수행한다.

 

(1, 1)은 1로 변했기 때문에 이전 (0, 1)로 돌아간다. 이후 dfs(x-1, y)를 수행하고...

 

...

 

위의 방식을 계속해서 재귀를 통해 0으로 연결된 모든 지점을 찾으며

 

return False를 받고 마지막 지점으로 돌아가는 포인트는

x, y의 경계선을 넘는 구간 (-1 or 최대 지점)

혹은

dfs(i, j)로 호출한 가장 첫 번째 함수가 호출되는 지점이 return True로 돌아오는 지점이 될 때까지 재귀로 반복하는 것이다.

 

이후 return True로 돌아오면 result += 1을 해주어 연결된 모든 지점을 찾은 후 카운트를 증가시켜준다.