문제 - 음료수 얼려먹기
-
N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
-
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 떄 생성되는 총 아이스크림의 개수를 구하라.
제한 사항
- 입력 조건 :
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
- 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
- 출력 : 한번에 만들 수 있는 아이스크림의 개수를 출력한다.
아이디어
-
모든 얼음 틀을 왼쪽 상단부터 반복문으로 검사한다. 만약 탐색하지 않은 공간이 있다면 그곳부터, DFS, BFS를 이용하여 탐색을 시작한다. 모두 탐색하고 나서 방문한 곳을 기록하고 아이스크림의 개수를 하나 증가시킨다.
-
더 이상 방문하지 않은 곳이 없으면 아이스크림의 개수를 반환한다.
코드
from typing import List
def solution(maps: List[List[int]], n: int, m: int) -> int:
def dfs(x, y):
if x <= -1 or x >= n or y <= -1 or y >= m:
return 0
if maps[x][y] == 0:
maps[x][y] = 1
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
return 1
return 0
cnt = 0
for x in range(n):
for y in range(m):
if dfs(x, y):
cnt += 1
return cnt
if __name__ == "__main__":
n, m = map(int, input().split())
maps = []
for _ in range(n):
maps.append(list(map(int, input())))
print(solution(maps, n, m))
배운점
- DFS 문제를 어떻게 풀어야할 지 대략적으로 감을 잡은 것 같다.
참고 문헌
>> Home