본문 바로가기
파이썬/코딩테스트

[파이썬] 코딩테스트 16 구현_음료수 얼려먹기☆

by nemonemonemo 2025. 8. 8.

문제

https://hongs-coding.tistory.com/52#google_vignette

 

[JAVA] 이.코.테 (DFS/BFS) - 음료수 얼려먹기

음료수 얼려 먹기 문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결

hongs-coding.tistory.com

음료수 얼려 먹기

문제

N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.

구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.

이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.

다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다

입력

  • 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
  • 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
  • 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력

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

입력 예시 1

4 5
00110
00011
11111
00000

출력 예시 1

3

입력 예시 2

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

출력 예시2

8

[문제 풀이 전략 정리] 얼음 틀 문제 (DFS/BFS)

문제 개요

  • 얼음 틀 모양의 2차원 배열이 주어진다.
  • 배열 안의 값이 0이면 구멍(얼음을 만들 수 있음), 1이면 칸막이(막혀 있음)이다.
  • 인접한 0끼리는 하나의 얼음 덩어리로 간주한다.
  • 이때, 만들 수 있는 얼음 덩어리의 개수를 구하는 문제다.

문제 풀이를 위한 전체 전략

이 문제는 탐색 알고리즘을 이용해서 풀 수 있다.

특히 DFS (깊이 우선 탐색) 또는 BFS (너비 우선 탐색) 을 사용할 수 있다.

해결 아이디어 요약

  1. 2차원 배열의 모든 칸을 출발점으로 삼아 탐색을 시도한다.
  2. 탐색은 해당 칸의 값이 0일 때만 시작한다. (1이면 칸막이라서 탐색할 수 없음)
  3. 탐색이 시작되면, 연결된 모든 0을 1로 바꾸며 하나의 얼음 덩어리를 완성시킨다.
  4. 하나의 탐색이 끝났다는 건, 하나의 얼음 덩어리를 완성했다는 의미이므로 카운트를 1 증가시킨다.

코드 흐름 및 설명

for i in 가로줄:
    for j in 세로줄:
        # (i, j) 위치의 모든 칸을 출발점으로 탐색
        # 이 칸의 값이 0이라면, 연결된 영역을 모두 방문한다
        # 연결된 0들을 1로 바꾸고, 얼음 개수를 +1 한다
  • 사각형의 모든 칸을 돌며 탐색 가능한 출발점을 찾는다.
  • 출발점은 항상 0이어야 하며, 이미 방문한 칸(1로 바뀐 칸)은 다시 탐색하지 않는다.
  • 탐색을 DFS 또는 BFS 방식으로 구현할 수 있다.

개념 이해를 위한 시뮬레이션 (예시: BFS 방식)

설명을 쉽게 하기 위해 배열의 좌표를 (1,1)부터 시작하는 것으로 가정한다.

(실제 코드에서는 (0,0)부터 시작한다)

  1. (1,1)에서 시작
    • 값이 0 → 탐색 시작 가능
    • 1로 바꾸고, 상하좌우(LRUD)로 이동 가능한 칸을 큐에 추가
  2. 큐에서 하나씩 꺼내며 다음 좌표 확인
    • 좌표가 배열 범위를 벗어나면 → PASS
    • 이미 1이라면 → PASS
    • 값이 0이면 → 1로 바꾸고, 다시 상하좌우로 확장
  3. 큐가 모두 비면, 하나의 얼음 덩어리 탐색 완료 → count += 1
더보기

얼음 틀 탐색 흐름 시뮬레이션 설명

문제 핵심 요약

  • 2차원 배열(지도)에 0은 구멍(얼음을 만들 수 있음), 1은 칸막이(못 감).
  • 인접한 0끼리는 하나의 덩어리로 취급한다.
  • 이 덩어리의 개수를 BFS 탐색으로 세는 것이 목표다.

탐색 흐름 이해하기

기준

  • 시뮬레이션은 (1,1)부터 (n,m)까지 가상의 좌표로 설명했지만, 실제 코드는 (0,0)부터 시작한다.
  • L은 큐(Queue)처럼 탐색해야 할 좌표를 담고 있는 목록이다.
  • 도장찍기란 방문한 곳을 1로 바꿔 다시 방문하지 않도록 만드는 것.
  • 방향은 L=왼쪽, R=오른쪽, U=위, D=아래를 뜻한다.

(1,1)에서 탐색 시작

(1,1) --> 출발 가능한 시작 체크 m(1,1) = 0
  • (1,1)의 값이 0이면 → 출발 가능!
  • 도장 찍기: m(1,1) = 1 (방문 처리)
  • 이 지점을 기준으로 4방향(LRUD)으로 갈 수 있는지 확인할 거야.

다음으로 갈 위치 추가 (할 일 목록)

L = [ (1,1)L, (1,1)R, (1,1)U, (1,1)D ]
  • (1,1)에서 4방향 위치를 리스트에 넣는다 (큐처럼 사용할 거야).

BFS 방식으로 하나씩 꺼내며 확인

  1. (1,1)L
  2. → (1,0)은 범위 밖 or 1이라서 PASS
  3. (1,1)R → (1,2)
    • 값이 0이므로 갈 수 있음!
    • 도장 찍기: m(1,2) = 1
    • 다음 할 일 목록에 (1,2) 기준으로 4방향 추가
L = [ (1,1)U, (1,1)D, (1,2)L, (1,2)R, (1,2)U, (1,2)D ]
  1. (1,1)U → (0,1)
  2. → 범위 벗어남 → PASS
  3. (1,1)D → (2,1)
    • 값이 0이므로 도장 찍기, 다음 할 일 추가
L = [ (1,2)L, (1,2)R, (1,2)U, (1,2)D, (2,1)L, (2,1)R, (2,1)U, (2,1)D ]

(1,2) 기준으로 이동 시작

  • (1,2)L → (1,1)은 이미 1 → PASS
  • (1,2)R → (1,3)은 1 → PASS
  • (1,2)U → (0,2) → PASS
  • (1,2)D → (2,2) → 0이므로 가능!
    • 도장 찍기
    • 다음 할 일 추가
L = [ (2,1)L, (2,1)R, (2,1)U, (2,1)D, (2,2)L, (2,2)R, (2,2)U, (2,2)D ]

(2,1) 방향들 처리

  • (2,1)L → PASS
  • (2,1)R → PASS
  • (2,1)U → PASS
  • (2,1)D → PASS
  • → 아무 곳도 새로 갈 수 없음

(2,2) 방향들 처리

  • (2,2)L → PASS
  • (2,2)R → (2,3) → 0 → 도장 찍기 + 다음 할 일 추가
L = [(2,2)U, (2,2)D, (2,3)L, (2,3)R, (2,3)U, (2,3)D]
  • (2,2)U → PASS
  • (2,2)D → PASS

(2,3) 방향들 처리

  • (2,3)L → PASS
  • (2,3)R → PASS
  • (2,3)U → PASS
  • (2,3)D → PASS
  • → 큐가 비었으므로 이 덩어리 탐색 완료!

얼음 덩어리 1개 완료!

(1,1)에서 출발한 탐색이 종료됨 → count += 1

다음 반복: (1,2), (1,3), (1,4)

  • 모두 이미 방문했거나 1이므로 PASS

(1,5)에서 새로 출발 가능

  • 값이 0 → 도장 찍기
  • 주변 살펴보니 전부 1이거나 범위 밖 → 할 일 없음
  • 바로 탐색 종료 → count += 1

다음 반복: (2,1)

  • 이미 방문함 → PASS

결론적으로는 

  • BFS는 한 지점에서 연결된 모든 0들을 한 번에 방문하고 다 도장 찍는다.
  • 다시 0인 칸을 만나기 전까지는 새로운 덩어리를 만들지 않는다.
  • 따라서, 새로운 0을 만날 때마다 덩어리 수를 +1 해주면 된다.

최종 코드

# BFS/DFS 탐색을 하는 경우가 여러번 사용될 예정 --> 함수화!!
# 입력 : 출발점에 대한 정보(row, col)좌표!!!
# 기능 : 입력의 출발점에서 시작이 가능한지 체크!!!!
#        --> 가능하다면,,,다 주어진 지도에서 1로 카드를 돌려두겠다!!!(도장!)
#        ==> 출발점에 가능한 연결된 모든 칸들을 다 탐색해서 돌리자!!
# 출력 : 입력의 출발점에 시작을 할 수 없다면,,,, : 0
#                                  수 있고, 다 끝나면 : 1
# ----------- : 개취!!!!

def bfs_ice( row_int, col_int):
    #1) 주어진 출발점 시작점에서 출발 할 수 있냐 체크
    # ==> 아웃바운드는 생각 안 해도 됨! -> 0으로 시작할 수 있냐만 생각하면 됨
    #     이 함수를 호출할 때 명확히 사각형 내부 좌표에서만 호출할 거니까
    if graph[row_int][col_int] == 0 :#--> 얼음 할 수 있는 공간이면
        #2) 방문할 곳들에 대한 세팅
        q = deque([[row_int, col_int]]) # -> 괄호 주의
        graph[row_int][col_int] = 1 # 도장찍기 -> 1로 뒤짚기
        # 할 일: graph에서 LRUD의 인접성을 체크 --> 할 일이 없을 때까지
        # ==> 연속된 것들에서 1로 변환할 것이 없을 때 까지

        #선호하지 않지만 이렇게 쓸 수도 있어
        while True:
            if not q :
                return 1 #종료 조건에 대한 세팅
            #열심히 할 일이 있다면...-> 할 일에 스케줄링 -> bfs/dfs 중 bfs
            row, col = q.popleft()
            #직접 연결된 LRUD에 대한 이동을 직접 체크하자
            #15번처럼 dx, dy를 만들어서 해도 되고
            #여기서 직접해도 된다 (방향은 별 상관 없음)
            for dx, dy in [[0,-1],[0,1],[-1,0],[1,0]]: # L R U D
                #--> cp1) 이동 가능한지 체크 : in/out
                if 0 <= row + d x < n and 0 <= col + dy < m: # 지도 안쪽
                    #-->cp2) 얼음을 얼릴 수 있는 공간이냐
                    if graph[row + dx][col + dy] == 0:
                        #새로운 공간/얼음 얼릴 수 있는 공간
                        graph[row + dx][col + dy] =1 # 도장찍기/카드 돌리기.
                        # 거기서 또 1칸 연결된 공간이 있는지 가서 체크--> 할 일 추가
                        q.append([row+dx, col+dy])
            else:
                #시작할 수 없는 출발점
                return 0
  • 코드만 정리
cnt = 0
for row in range(n):
    for col in range(m):
        #개취-> 모든 점을 다 시작점으로 탐색을 요청
        #=> 개선하고자 하시면 여기서 필터링 해서 시작할 수 있을 때만 탐색
        cnt += bfs _ice(row, col) #if graph[row][col]==0:
print(cnt)

DFS + 재귀함수 방식으로 풀어보기

 

함수 구조 분석

def dfs_re(row, col):
    # (1) 범위 밖이면 종료
    if row <= -1 or row >= n or col <= -1 or col >= m:
        return False

    # (2) 범위 안이고, 얼릴 수 있는 곳(0)이면
    if graph[row][col] == 0:
        # (2-1) 방문 도장 찍기 (1로 바꾸기)
        graph[row][col] = 1
        
        # (2-2) 네 방향으로 계속 탐색 (재귀 호출)
        dfs_re(row, col - 1)  # 왼쪽
        dfs_re(row, col + 1)  # 오른쪽
        dfs_re(row - 1, col)  # 위쪽
        dfs_re(row + 1, col)  # 아래쪽
        
        # (2-3) 얼음 하나 완성! (True 반환)
        return True

    # (3) 이미 방문했거나, 얼릴 수 없는 곳이면 False 반환
    return False
 

이 함수의 목적

  • 2차원 리스트 graph에서 0은 아직 얼지 않은 부분, 1은 이미 얼음이 있는 부분
  • 연결된 0들을 한 덩어리로 얼려서 얼음 하나를 만드는 게 목표
  • 이 함수는 (row, col)에서부터 시작해서, 주변에 연결된 모든 0을 1로 바꿈

함수 동작 순서

예를 들어, 이렇게 생긴 얼음틀이 있다고 하자(n=3, m=3):

graph = [
  [0, 0, 1],
  [1, 0, 1],
  [0, 1, 0]
]
  1. dfs_re(0, 0)을 부르면,
  2. 현재 위치가 0이면 1로 바꾸고,
  3. 왼쪽/오른쪽/위/아래로 또다른 0이 있는지 계속 확인!
  4. 재귀 함수로 계속 깊숙이 들어감. 마치 한 방향으로 계속 뻗어나가듯이!
  5. 더 이상 갈 곳이 없으면 되돌아오고, 탐색이 끝난 곳은 모두 1로 바뀜.

재귀 함수 구조 이해 포인트

구분 설명
if graph[row][col] == 0: 현재 위치가 '아직 얼지 않은 곳'이라면
graph[row][col] = 1 방문 도장 찍기 (다시 방문 못하게!)
dfs_re(…) 4번 호출 네 방향으로 또 탐색 (왼, 오, 위, 아래)
return True 얼음을 하나 새로 만들었다는 뜻
return False 이미 얼었거나, 범위 밖이라면 더 이상 탐색X
 

재귀 vs DFS(반복문)의 차이

재귀 함수 DFS 반복문
함수 안에서 자기 자신을 다시 호출 스택 구조로 직접 관리 (stack.push/pop)
코드가 간결하고 직관적 복잡한 구조도 컨트롤 가능
시스템 스택 사용 → 너무 깊어지면 오류 발생 가능 깊이 조절 가능
 

포인트

  • 방향성이나 순서가 중요하지 않기 때문에, DFS든 BFS든 상관없이 풀 수 있음.
  • 단, 이 코드는 DFS 재귀 방식을 사용해서, L → R → U → D 순서로 탐색함.
  • 탐색 순서를 바꾸고 싶으면 dfs_re() 호출 순서를 바꾸면 된다!

'파이썬 > 코딩테스트' 카테고리의 다른 글

[파이썬] 코딩테스트 17 기출_ 소수 구하기 문제  (3) 2025.08.11
[파이썬] 코딩테스트 15 구현_미로탐색 ☆  (2) 2025.08.07
[파이썬] 코딩테스트 14 구현_최단거리 ☆  (0) 2025.08.07
[파이썬] 코딩테스트 13 구현_BFS  (1) 2025.08.07
[파이썬] 코딩테스트 12 구현_DFS  (2) 2025.08.07

관련글

티스토리툴바