[백준] 4963. 섬의 개수 python

🐳 링크

백준 4963번 섬의 개수

🐕 문제

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

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

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

🐾 풀이 방법

그래프 문제 중 간단한 문제이다.
dx, dy에 상하좌우 + 대각선을 추가하여 자신 기준으로 총 8번을 탐색할 수 있도록 해준다. 연결되어있으면 계속 진행하고, 대신 자신을 0으로 만든 뒤 다음 노드로 진행해준다. 이미 연결되었다고 생각하므로 graph에서 0값으로 바꾸어주는 것이다.
dfs가 한번 종료되면, cnt를 1 증가 시켜준다.

solution 코드

import sys
sys.stdin = open("input.txt","rt")
sys.setrecursionlimit(10**5)

dx = [-1, 1, 0, 0, -1, 1, -1, 1]
dy = [0, 0, -1, 1, -1, 1, 1, -1]

def dfs(x,y):
    visit[x][y] = 1

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and visit[nx][ny] == 0 and graph[nx][ny] == 1:
            graph[nx][ny] = 0
            dfs(nx,ny)


while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0:
        break

    visit = [[0] * w for _ in range(h)]
    graph = []
    for _ in range(h):
        graph.append(list(map(int, sys.stdin.readline().split())))

    cnt = 0
    for i in range(h):
        for j in range(w):
            if visit[i][j] == 0 and graph[i][j] == 1:
                dfs(i, j)
                cnt += 1

    print(cnt)