이코테 - 음료수 얼려먹기2 - DFS - 2021/03/11

leehojin0719.tistory.com/31

이코테 - 음료수 얼려먹기 - DFS - 2021/03/10

여기서 풀었던 음료수 얼려먹기 문제는 상하좌우 검사할 때,

 

dfs(x-1,y)

dfs(x,y-1)

dfs(x+1,y)

dfs(x,y+1)

 

로 풀었던 문제를 dx와 dy로 풀어봤다.

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
    
def dfs(x, y):
    graph[x][y] = 1
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx <= -1 or nx >= n or ny <= -1 or ny >= m:
            continue
        if graph[nx][ny] == 1:
            continue
        if graph[nx][ny] == 0:
            dfs(nx, ny)
            
            
count = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            count += 1
            dfs(i, j)
print(count)

 

main문부터 

1. 전 좌표를 다 검사한다.

2. 만약 좌표 값이 0이면 카운트하고 dfs함수를 이용한다. (->dfs함수안에서 인접한 0들은 다 1로 바뀐다.)

 

dfs함수에서

1. 0이었던 입력된 좌표의 값을 1로 바꾼다 (->재귀함수 이용시 인접한 0들을 1로 바꾸기 위해)

2. dx와 dy를 정의하고

3. 네 방면으로 모두 새로운 nx와 ny를 만들어준다.

4. 첫 번째 if문에서 좌표를 벗어나면 continue한다.

5. 두 번째 if문에서 벽을 만나면 continue한다.

6 세 번째 if문에서 0이면 재귀함수를 이용한다.