[백준] 4963 파이썬(python) : 섬의 개수 - (방향벡터, 대각선)

4963번: 섬의 개수

 

 

import sys
sys.setrecursionlimit(10**5)

def dfs(x, y):
    dx = [ -1, 1, 0, 0, -1, -1, 1, 1 ] #1
    dy = [ 0, 0, -1, 1, -1, 1, -1, 1 ]

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and not visit[nx][ny]:
            if graph[nx][ny] == 1:
                visit[nx][ny] = True
                dfs(nx, ny)

while True:
    w, h = map(int, sys.stdin.readline().split())
    if w == 0 and h == 0: #2
        break
    graph = [  ]
    visit = [ [False]*(w) for _ in range(h) ] #3
    for i 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 graph[i][j] == 1 and not visit[i][j]:
                visit[i][j] = True #4
                dfs(i, j)
                cnt += 1
    print(cnt)

 

#1 : 대각선을 움직이기 위해 리스트 8개 생성

#2 : 탈출조건

#3 : 방문처리를 위한 리스트

#4 : 첫 위치 방문처리

 

이전 문제들과 다르게 대각선도 표현해줘야 하는 문제였다. 그것 말고는 특별한것이 없는 문제였는데 여러 문제를 풀면서도 느끼지만 테스트 케이스만큼 입력해줘야하는 문제가 싫다. 깔끔하지 못해서 그런가 while문을 만들고 탈출조건을 만들어야 하니 번거롭다고 생각한다.

 

bfs풀이 - 23.01.14(토)

import sys
from collections import deque
while True:
    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) ]
    dx = [ 0, 0, -1, 1, -1, -1, 1, 1 ]
    dy = [ -1, 1, 0, 0, -1, 1, -1, 1 ]
    visit = [ [False] * w for _ in range(h) ]
    def bfs(x, y):
        q = deque()
        q.append((x, y))
        while q:
            x, y = q.popleft()
            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] == False and graph[nx][ny] == 1:
                    visit[nx][ny] = True
                    q.append((nx, ny))
    count = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1 and visit[i][j] == False:
                visit[i][j] = True
                bfs(i, j)
                count += 1
    print(count)