이것저것 개발 블로그

"이것이 코딩테스트다" 책 문제 _ DFS/BFS 문제

NxM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생서오디는 총 아이스크림의 개수를 구하는 프로그램을 작성해라.

예시) 4x5 얼음틀 : 아이스크림 3개 생성

입력조건

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

출력조건

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

풀이)

이 문제는 DFS로 풀어보았다! 전형적인 문제가 아닐까 생각한다.

N, M = map(int, input().split())
ice = []
for i in range(N):
    ice.append(list(map(int, input())))


def dfs(x, y):
    global N, M
    if x < 0 or x >= N or y < 0 or y >= M:
        return False
    if ice[x][y] == 0:
        ice[x][y] = 1
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False

count = 0
for i in range(N):
    for j in range(M):
        if dfs(i, j) == True:
            count += 1

print(count)

얼음판 ice 구조를 이중 list로 저장해주고, (0, 0)부터 차례로 순회한다.

순회할때는 좌표 범위를 확인하고 0일경우 1로 바꿔준다.

dfs를 실행중인 좌표 기준으로 좌, 우, 상, 하를 똑같이 dfs로 순회한다.

return 값이 True로 끝나면 순회 완료! False 일 경우는 범위를 넘었거나 1인 경우이다.

또한 BFS로도 풀어보았다!!! (책은 DFS에 해당하는 풀이만 나와있다.)

from collections import deque

N, M = map(int, input().split())
ice = []
for i in range(N):
    ice.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(i, j):
    queue = deque()
    if ice[i][j] == 0:
        queue.append([i, j])
        while queue:
            x, y = queue.popleft()
            for p in range(4):
                nx = x + dx[p]
                ny = y + dy[p]
                if 0 <= nx < N and 0 <= ny < M:
                    if ice[nx][ny] == 0:
                        ice[nx][ny] = 1
                        queue.append([nx,ny])
                    else:
                        continue
                else:
                    continue
        return 1
    else:
        return 0



count = 0
for i in range(N):
    for j in range(M):
        count += bfs(i, j)
print(count)

좌, 우, 상, 하 이동을 dx, dy를 생성하여 만들었다. dfs와 같이 순회는 (0, 0) 부터 시작한다.

Ice가 0일 경우만 queue에 삽입 후 bfs를 진행하고, 아닐 경우는 없는 경우로 판단해 return 0한다.

다음 좌표의 ice가 0일 경우 1로 바꾸고 queue에 삽입한다. 이것을 queue가 다 끝날때까지 반복!

queue가 다 끝나면 해당 좌표의 bfs가 끝난 것이므로 1을 return해준다.

그리고 bfs 개수를 모두 더해주면 끝!!