[BOJ] 4963 : 섬의 개수 - 파이썬(Python)

문제 해석

---

 

대각선을 포함해서 인접한 노드를 찾는 탐색문제였다.

대각선까지 탐색하는 문제는 처음이였지만 어차피 대각선 인덱스만 추가로 탐색을 해주면 되는 것이기 때문에 

풀이 자체는 어렵지 않았다.

 

문제 풀이

---

import sys
from collections import deque


def BFS(x, y):
    dx = [-1, -1, -1, 0, 0, 1, 1, 1]
    dy = [-1, 0, 1, -1, 1, -1, 0, 1]
    deq = deque()
    deq.append((x, y))
    graph[x][y] = 0
    while deq:
        x, y = deq.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                deq.append((nx, ny))


answer = []
while True:
    result = 0
    W, H = map(int, sys.stdin.readline().split())

    if W == 0 and H == 0:
        break

    graph = [list(map(int, sys.stdin.readline().split())) for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if graph[i][j] == 1:
                BFS(i, j)
                result += 1
    answer.append(result)

for a in answer:
    print(a)

 

BFS를 이용해서 풀었다.

그런데 문제를 여러번 고쳐서 풀었다.

이유는 문제에서 그래프의 크기가 1 x 1 일 경우에 그냥 0을 입력하는 부분을

과거에 학교에서 C언어 실습문제를 풀듯이 H의 크기가 1보다 큰 경우와 작거나 같은 경우를 나눠서

작거나 같은 경우 그냥 0을 받기만 해줄 변수에 대한 입력을 하나 더 만들었는데 

그게 오답으로 나오는 원인이였다.