[알고리즘] 백준 4963 파이썬 - 섬의 개수

 

4963번: 섬의 개수

문제

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

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

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

 

 

문제풀이

from collections import deque
import sys
input=sys.stdin.readline

def bfs(graph,x,y):
	#03
    dx=[-1,1,0,0,1,1,-1,-1]
    dy=[0,0,-1,1,-1,1,-1,1]
    graph[x][y]=0
    q=deque([(x,y)])
    while q:
        x,y=q.popleft()
        for i in range(8):
            nx=x+dx[i]
            ny=y+dy[i]
            #04
            if 0<=nx<h and 0<=ny<w and graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=0
    return
    
while True:
    w,h=map(int,input().split())
    #01
    if w==0 and h==0:
        break
    graph =[]
    for i in range(h):
        graph.append(list(map(int,input().split())))
    cnt=0
    #02
    for i in range(h):
        for j in range(w):
            if graph[i][j]==1:
                bfs(graph,i,j)
                cnt+=1
    print(cnt)

- #01 :w와 h가 0이면 while문을 종료한다.

          graph에 입력받은 값들을 추가해준다. 

- #02 : for문을 통해 0,0 부터 h-1,w-1까지 graph 값이 1인 것을 찾는다.

           1이라면 bfs 함수를 실행하고, cnt를 1 늘린다.

           for문이 끝나면 cnt를 출력한다.

- #03 : dx,dy는 가로, 세로, 대각선 모두 움직일 수 있는 좌표들을 저장한 값이다.

           bfs가 실행되었다는 것은 graph[x][y]가 1이라는 것이니, 해당 값을 0으로 바꿔준다.

           q에는 초기값으로 (x,y)를 넣어준다. for문을 통해 nx와 ny라는 새로운 좌표값을 얻는다.

- #04 : 해당 좌표값이 조건을 만족하면 q에 추가하고, graph[nx][ny]는 0으로 바꿔준다.

           즉 bfs 함수는 인접한 땅을 모두 0으로 바꾸어 각각의 섬의 개수를 얻을 수 있다.