[boj] 백준 2792 보석 상자 python 풀이

문제

 

https://www.acmicpc.net/problem/2792

2792번: 보석 상자

 

 

문제 풀이

가장 큰 섬을 찾는 bfs 문제

 

코드

import sys
input = sys.stdin.readline
import collections

N, M = map(int,input().split())
MAP = [list(map(int,input().split())) for _ in range(N)]
T = int(input().strip())

def bfs(visited, i, j):
    move = {(-1,0), (0,3), (1,0), (0,-3)}

    q = collections.deque()
    q.append((i,j))
    visited[i][j] = 1

    while q:
        x,y = q.popleft()

        for tx, ty in move:
            nx = tx + x
            ny = ty + y

            if 0<=nx<N and 0<=ny<M*3 and visited[nx][ny] == 0:
                if (MAP[nx][ny] + MAP[nx][ny+1] + MAP[nx][ny+2]) / 3 >= T:
                    q.append((nx,ny))
                    visited[nx][ny] = 1

island_cnt = 0
visited = [[0 for _ in range(M*3)] for _ in range(N)]
for i in range(N):
    for j in range(0,M*3,3):
        if visited[i][j] == 0 and (MAP[i][j] + MAP[i][j+1] + MAP[i][j+2]) / 3 >= T:
            bfs(visited, i, j)
            island_cnt += 1
        
print(island_cnt)