💥이코테 실전문제 뽀개기💥

💻 5-1 음료수 얼려 먹기

난이도🖤🖤🖤🤍🤍🤍 | 풀이시간 30분 | 제한시간 1초 | 메모리제한 128MB

---

📌2021/01/21 작성 코드

def dfs(graph, row, col, visited):
    # 현재 노드를 방문 처리
    visited[row][col] = True
    # print((row, col), end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    # 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주
    # 상
    if 0 <= row - 1 < n and graph[row-1][col] == 0:
        if not visited[row-1][col]:
            dfs(graph, row-1, col, visited)
    # 하
    if 0 <= row + 1 < n and graph[row+1][col] == 0:
        if not visited[row+1][col]:
            dfs(graph, row+1, col, visited)
    # 좌
    if 0 <= col - 1 < m and graph[row][col-1] == 0:
        if not visited[row][col-1]:
            dfs(graph, row, col-1, visited)
    # 우
    if 0 <= col + 1 < m and graph[row][col+1] == 0:
        if not visited[row][col+1]:
            dfs(graph, row, col+1, visited)

# 입력
n, m = map(int, input().split())
tray = [list(map(int, input())) for _ in range(n)]
visited = [[False for _ in range(m)]for _ in range(n)]
# 실행 횟수
answer = 0
# dfs 함수 호출
for i in range(n):
    for j in range(m):
        if tray[i][j] == 0 and not visited[i][j]:
            answer += 1
            dfs(tray, i, j, visited)
# 출력
print(answer)

---

💭 아이디어

트레이 전체를 큰 그래프로 두고 DFS(해설을 참고해서 DFS로 결정함... 딱히 다른 이유는 없었다) 실행.

트레이 전체를 순회하면서, 트레이의 상태가 0이고, and visited 처리 안 된 node를 시작 node로 삼아 DFS를 실행한다.

DFS의 실행 횟수가, 바로 얼음을 얼릴 수 있는 공간의 개수이다.

---

🤓 문제 해설

1) 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

2) 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.

3) 1~2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

---

🤓 답안 예시

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

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

# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문
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):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1

print(result) # 정답 출력

---

🤔 리뷰

• 답안 예시에서는 아예 dfs함수에 진입하자마자 주어진 범위를 벗어나는지 확인해보고 아니면 False를 return했다. 이로 인해 코드 길이를 많이 줄일 수 있었던 것 같다.
• 답안 예시에서는 visited 리스트를 따로 만들지 않고, graph에 직접 방문한 것은 1로 표시해서 다시 방문하지 못하게 만들었는데, 이것도 좋은 아이디어인 것 같다.
• 사실 DFS/BFS에 익숙하지 않아서 처음에 문제를 보고 막막했다. 해설 보고 어떤 것을 적용해야 할지 알게 된 문제이다. 쉬운 DFS/BFS 문제부터 여러 번 풀어봐야겠다.