4963 섬의 개수

1. 문제

문제는 링크를 들어가면 볼 수 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

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

def bfs(graph,y,x,summation):

    q = deque()
    graph[y][x] = 0 # 방문처리
    q.append([y,x])

    while q : # 큐가 빌 때까지
        now = q.popleft()
        for n in range(8):
            ny = now[0] + dy[n]
            nx = now[1] + dx[n]

            if nx <0 or ny <0 or nx >= W or ny >= H :
                continue

            if graph[ny][nx] == 1 : # 땅이라면 밟자.
                graph[ny][nx] = 0
                q.append([ny,nx])

        # while 한번이 한 뭉탱이가 끝나는 것
    summation += 1

    return summation



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

summation_array = []
while True :

    summation = 0
    W,H = map(int,read().split())
    if W == 0 and H == 0 :
        break
    else :
        graph = []
        for h in range(H):
            graph.append(list(map(int,read().split())))
        for y in range(H):
            for x in range(W):
                if graph[y][x] == 1 : # 땅이라면 bfs 실행
                    summation = bfs(graph,y,x,summation)
                    # for mm in range(H):
                    #     print(graph[mm])
                    # print()
    summation_array.append(summation)

for kk in summation_array:
    print(kk)

3. 문제 풀이

문제가 어려운건 아닌데, 대각선이 추가되었다는 점이 새롭다. 기본적인 BFS를 사용하면 쉽게 풀 수 있다. 근데 이상한게 DFS분류를 들어와서 문제를 푸는데, 왜 BFS가 제일 편한지 모르겠다..