[DFS/BFS] 음료수 얼려 먹기

문제링크

- 이것이 코딩 테스트다 에서의 예제 문제이다

 

해설

# 한 덩어리 찾고 다음 덩어리 찾고 ...
# DFS 로 생각하는게 맞을 듯?

dy = (0, 1, 0, -1)
dx = (-1, 0, 1, 0)

def is_valid_coord(x, y):
    return 0 <= x < n and 0 <= y < m

def dfs(x, y):
    if is_valid_coord(x, y) == False:
        return False
    
    if graph[x][y] == 0:
        # 해당 노드 방문처리
        graph[x][y] = 1

        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            dfs(nx, ny)
    
        return True
    return False

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

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

 

총평/느낀점

생각하는 과정이 아직도 어렵게 느껴진다.

모두 다 이 과정에서 크게 달라지지 않는다는 것을 기억하자

 

출처

이것이 코딩 테스트다