[백준] 섬의 개수(4963번)

[출처] https://www.acmicpc.net/

알고리즘 분류 : 그래프 이론, 그래프 탐색

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

[출처] https://www.acmicpc.net/problem/4963

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입출력

접근

주어진 그림을 보면 바로 격자형 그래프를 떠올릴수 있을것이다.

문제에서 가로세로 대각선은 걸어갈수 있다라고 했기 때문에 각 칸을 노드로 생각하면 인접한 노드는 최대 상하좌우+대각선 4개 = 8개가 나오는 그래프라고 생각할 수 있다.

이렇게 그래프로 보면 굉장히 단순하다

'섬의 갯수가 몇개냐' 라는 문제인데, 이를 그래프로 볼수 있으면 '주어진 그래프에서 연결요소의 개수가 몇개냐'라는 말과 동일하다.

즉, 이 문제는 11724번의 문제와 동일하다고 생각할수 있다.
단지 11724번은 일반적인 형태의 그래프을 준것이고, 이 문제는 격자형 그래프(좌표평면식)로 주어진 것이다.

접근 아이디어는 다음과 같다.

1. 그래프 만들기

우선 탐색을 하기에 앞서서 탐색할 그래프를 만들어야된다.

아래 코드와 같이 지도의 너비와 높이를 입력받아서 2차원 배열로 만들어준다.

#지도의 너비(w)와 높이(h)
    w,h = map(int,sys.stdin.readline().split())

    #둘다 0이면 종료
    if w == 0 and h == 0:
        break
    #지도
    graph = list()

    for _ in range(h):
        #지도를 만듦
        temp = list(map(int,sys.stdin.readline().split()))
        graph.append(temp)

2. bfs 탐색할 시작노드 선정

한점에서 부터 갈수 있는 모든 노드를 탐색하고, 탐색된 노드들은 전체 노드에서 빼주어야된다.
이를 위해서 탐색할 노드를 선정해야된다.

반복문을 이용하여 (0,0)부터 (h,w)까지 확인하면서 섬인 노드 즉, 값이 1인 노드이면 시작노드로 넣어서 bfs를 탐색하게 한다.

현재 노드에서 인접노드를 구하기 위해서 다음 코드와 같이 상하좌우 대각선, 총 8개를 리스트에 담아주었다.

탐색이 필요한 노드가 담긴 need_visited에서 노드를 꺼내고, 해당 노드에서 8가지의 경우에 대해서 이동한 좌표를 순서대로 검사하고, 지도상에 있고, 땅인 좌표이면 방문처리후 다음 탐색을 위해서 need_visited에 넣어주었다.

def bfs(start_node:tuple, graph:list) -> list:

    #상하좌우 대각선
    dx = [ 0,0,-1,1,-1,-1, 1, 1]
    dy = [-1,1, 0,0,-1, 1,-1, 1]

    #따로 방문체크할 노드가 필요없음, 지도를 보면서 탐색하면 0으로 바꿀것이므로 지도에 방문체크가 이루어짐
    
    #다음 탐색이 필요한 노드 저장
    need_visited = deque(list())

    #시작노드를 넣음
    need_visited.append(start_node)
    
    #시작노드 방문처리
    graph[start_node[0]][start_node[1]] = 0

    #탐색 시작
    while need_visited :

        #높이와 넓이 - 행과 열
        current_h,current_w = need_visited.popleft()

        for i in range(len(dx)):
            next_h = current_h + dx[i]
            next_w = current_w + dy[i]

            #지도의 크기를 넘어가지 않으면 추가
            if next_h >= 0 and next_h < len(graph) and next_w >= 0 and next_w <len(graph[0]):

                #다음에 탐색할 위치가 땅(1)이면 추가
                if graph[next_h][next_w] == 1:

                    #방문처리
                    graph [next_h][next_w] = 0
                    #다음 탐색을 위해 추가
                    need_visited.append((next_h,next_w))
    
    return graph

3. 섬의 개수 세기

탐색이 끝나면 count변수에 +1해서 섬의 개수를 세어준다.

4. 탐색한 노드 제거

다음 탐색을 위해서 bfs탐색시에 탐색한 섬은 전부 0으로 변경해주고, 그래프정보(지도정보)를 업데이트 해준다.

위와 같은 과정을 반복하면 지도를 남김없이 탐색하면서 섬의 개수를 셀수 있다.

전체 코드는 다음과 같다.

import sys
from collections import deque

#bfs 함수 정의 - graph를 반환해서 업데이트함, 탐색시작노드는 좌표이므로 튜플로 받음

def bfs(start_node:tuple, graph:list) -> list:

    #상하좌우 대각선
    dx = [ 0,0,-1,1,-1,-1, 1, 1]
    dy = [-1,1, 0,0,-1, 1,-1, 1]

    #따로 방문체크할 노드가 필요없음, 지도를 보면서 탐색하면 0으로 바꿀것이므로 지도에 방문체크가 이루어짐
    
    #다음 탐색이 필요한 노드 저장
    need_visited = deque(list())

    #시작노드를 넣음
    need_visited.append(start_node)
    
    #시작노드 방문처리
    graph[start_node[0]][start_node[1]] = 0

    #탐색 시작
    while need_visited :

        #높이와 넓이 - 행과 열
        current_h,current_w = need_visited.popleft()

        for i in range(len(dx)):
            next_h = current_h + dx[i]
            next_w = current_w + dy[i]

            #지도의 크기를 넘어가지 않으면 추가
            if next_h >= 0 and next_h < len(graph) and next_w >= 0 and next_w <len(graph[0]):

                #다음에 탐색할 위치가 땅(1)이면 추가
                if graph[next_h][next_w] == 1:

                    #방문처리
                    graph [next_h][next_w] = 0
                    #다음 탐색을 위해 추가
                    need_visited.append((next_h,next_w))
    
    return graph

while True:
    #지도의 너비(w)와 높이(h)
    w,h = map(int,sys.stdin.readline().split())

    #둘다 0이면 종료
    if w == 0 and h == 0:
        break
    #지도
    graph = list()

    for _ in range(h):
        #지도를 만듦
        temp = list(map(int,sys.stdin.readline().split()))
        graph.append(temp)

    count = 0
    #반복문을 돌면서 땅인부분(1)을 찾게 되면 그 점부터 bfs탐색을 함.
    for i in range(h):
        for j in range(w):
            #지도가 1이면 그점부터 탐색시작
            if graph[i][j] == 1:
                graph = bfs((i,j),graph)
                #탐색이 끝나면 섬의 개수 +1
                count += 1

    print(count)

결과

기본적인 그래프 탐색 문제였고, 다만 주어지는 그래프가 격자형으로 주어져서 이를 일반적인 노드와 간선으로 이루어진 그래프 처럼 생각할수 있는지가 중요한 문제였던것 같다.