이코테-음료수 얼려먹기 (파이썬)

첫 시도 : 上

이해도 하지 못했다. 그냥 읽었을 뿐

 

두번째 시도 : 中

일부가 보였다. 약간 부분적으로 이해는 했으나 전체적으로 이해를 못했다.

약간 이해해도 곧바로 까먹었다.

 

세번째 시도 : 下

전체가 보였다. 전체적인 흐름을 읽을 수 있다.

이런 유형. 이제 코드도 짤 수 있다.

 

DFS를 이용하는 문제

 

---

 

예를 들어서 3x3 틀이 있다고 가정했을 때

0과 1로 채울 수 있다. 1은 틀. 즉, 막힌 부분이고 0은 다 연결되어 있는 부분이다.

얼음을 얼렸을 때 몇개의 얼음을 만들 수 있는지 그런 문제다.

 

좀 더 직관적으로 보면

아래와 같은 예시에서는 총 3개의 얼음을 만들 수 있다.

---------

0 0 1

0 1 0

1 0 1

---------

 

원리

2차원 리스트를 만들고 (x, y)가 0이면 1로 바꾸고 주위에도 1로 꽉 채운다.

 

그렇게 해당 (x,y)좌표에서 시작된 여정이 근처에 있는 것을 다 1로 바꾸고 나면 result 값이 1늘어나게 하고 다른 (x,y)좌표에도 0인지 1인지 확인해서 1이면 pass하고 0이면 다시 여정을 시작하게 함으로서 2차원 리스트를 모두 다 1로 만들어 나간다.

그 다음 결과적으로 다 더한 result값을 print한다.

 

코드

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

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

def dfs(x, y):
    if x<= -1 or y <= -1 or x >= n 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




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