음료수 얼려 먹기

Chori·2024년 10월 4일

BFS DFS 탐색

[학습] 이것이 취업을 위한 코딩 테스트다 with 파이썬

목록 보기

11/24

이것이 취업을 위한 코딩 테스트다 with 파이썬을 공부하면서 정리한 내용입니다.

문제 내용

$N \times M$ 크기의 얼음 틀이 있음
구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시됨
구멍이 뚫린 부분끼리 상하좌우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주
얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램 작성

입력 조건

첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어짐
두 번째 줄 부터 N + 1번째 줄까지 얼음 틀의 형태가 주어짐
이때, 구멍이 뚫린 부분은 0, 그렇지 않은 부분은 1

출력 조건

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

입력 예시 1

출력 예시 1

입력 예시 2

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력 예시 2

문제 해설

얼음을 얼릴 수 있는 공간이 상하좌우로 연결되어 있으니 그래프 형태로 모델링
0인 값이 상하좌우로 연결되어 있는 노드를 묶고 이러한 묶음을 찾으면 됨
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)

다른 풀이

BFS 알고리즘 이용
특정한 칸에서 상하좌우로 움직일 때 좌표가 어떻게 바뀌는지 dx와 dy로 정의
탐색하지 않은 칸이 있으면 해당 칸의 좌표를 큐에 넣음
큐가 빌 때까지 아래 과정 반복
1. 큐에서 좌표를 꺼내면서 해당 칸을 방문 처리
2. 특정 칸의 상하좌우에 방문하지 않은 칸이 있으면 큐에 해당 칸의 좌표 삽입
이중 반복문에서 bfs()를 호출하여 처음부터 마지막 칸까지 모두 1로 만듦

소스 코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().rstrip().split())

graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    if graph[x][y] == 1:
        return False
    
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()
        graph[x][y] = 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <= (n - 1) and 0 <= ny <= (m - 1) and graph[nx][ny] == 0:
                queue.append((nx, ny))
    return True

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

print(result)