4963

날짜 : 2022. . 

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

def bfs(a, b, idx):
    queue.append([a, b])
    earth[a][b] = idx
    dx = [1, -1, 0, 0, 1, 1, -1, -1]
    dy = [0, 0, 1, -1, 1, -1, 1, -1]

    while queue:
        temp = queue.popleft()
        #print(temp)
        for i in range(8):
            x = temp[0] + dx[i]
            y = temp[1] + dy[i]
            if x in range(h) and y in range(w): # 범위에 있는 경우
                if earth[x][y] == 1:
                    earth[x][y] = idx
                    queue.append([x, y])
    return


while True:
    w, h = map(int, sys.stdin.readline().split()) # 너비, 높이
    if w == h and w == 0: break
    earth = []
    queue = deque()
    cnt = 2
    for _ in range(h):
        earth.append(list(map(int, sys.stdin.readline().split()))) # 입력
    for i in range(h):
        for j in range(w):
            if earth[i][j] == 1:
                bfs(i, j, cnt)
                cnt += 1
    """for i in earth:
        print(i)"""
    res = max(map(max, earth))
    if res == 0: print(res)
    else: print(res - 1)

 

 

풀이

- 평소에 풀어보았던 BFS 문제

- 다만 방향이 대각선까지 포함되었기 때문에 해당 케이스들을 이동방향을 저장하는 리스트에 넣어 저장 후 연산하는 것이 차이점이었다.

 

 

알게된 점

- 

 

 

참고 사이트

-