문제
문제
N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다
입력
첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
출력
한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
입력 예시
4 5
00110
00011
11111
00000
출력 예시
3
풀이
이것이 코딩 테스트다에서 배웠던 DFS를 그대로 활용해서 문제를 풀면 간단하게 풀 수 있다.
특정 지점에서 상하좌우를 모두 살펴보고 살펴본 지점이 0이면 그 지점을 방문 후 또다시 상하좌우를 방문하는 과정을 반복해 나가면 답을 구할 수 있다.
과정
1. 특정 지점에서 상하좌우로 탐색을 시작한다.
2. 탐색한 지점이 0이면 그 지점을 방문처리 후 1번 과정을 반복한다.
3. 방문 후에는 방문 지점을 1로 하여 방문처리를 하므로 다음 과정에서 True를 리턴하지 않게 된다.
4. 전체적으로 탐색을 진행하면서 True값이 리턴될 때 마다 answer을 하나씩 증가시킨다.
5. 탐색 종료 후 answer을 출력한다.
정답 코드
n,m = map(int,input().split())
graph = []
for i in range(n):
graph.append(list(map(int,input())))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def dfs(x,y):
if x < 0 or x >= n or y < 0 or y >= m:
return False
if graph[x][y] == 0:
graph[x][y] = 1
dfs(x + 1,y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
return True
return False
answer = 0
for i in range(n):
for j in range(m):
if dfs(i,j) == True:
answer += 1
print(answer)
