[백준] 2468 - 안전 영역

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

 

알고리즘

BFS

 

풀이 

만만하게 보면 안되는 문제!!!!

N은 보드의 너비 (N x N 크기의 보드)

 

연결요소의 개수를 구하는 문제처렁 평이하게 BFS 코드를 짠다... 

But, 연결요소의 개수를 구할 때 보드에서 1, 0으로 정점간의 연결을 처리하는 것과 달리

height 라는 높이 변수를 주고, height 이상이면 1, 미만이면 0으로 생각하면 편하다.

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)

def is_valid_coord(x, y):
    return 0 <= x < N and 0 <= y < N

def bfs(x, y):
    dq = deque()
    dq.append((x, y))
    
    while dq:
        x, y = dq.popleft()
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            
            if is_valid_coord(nx, ny) and not chk[nx][ny] and board[nx][ny] > height:
                chk[nx][ny] = True 
                dq.append((nx, ny))

 

 

height를 1~100 까지 for 문을 돌리면서 초기화해주고,

연결요소의 개수가 이전 height의 연결요소의 개수보다 크면 초기화해준다.

res = 1 # 최댓값으로 업데이트

for height in range(1, 101): # 1~100
    ans = 0 # 연결요소의 개수
    chk = [[False] * (N) for _ in range(N)]
    
    for i in range(N):
        for j in range(N):
            if not chk[i][j] and board[i][j] > height:
                ans += 1 
                bfs(i, j)
    
    res = max(res, ans)

print(res)

 

보드의 크기 N을 height로 두고 풀었다가 틀렸다 ㅠㅠ 

 

전체 코드

# 안전 영역 
# BFS
# N 이상을 1로, N 이하를 0으로 생각 
# 연결요소의 !최대! 개수 

from collections import deque

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)

def is_valid_coord(x, y):
    return 0 <= x < N and 0 <= y < N

def bfs(x, y):
    dq = deque()
    dq.append((x, y))
    
    while dq:
        x, y = dq.popleft()
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            
            if is_valid_coord(nx, ny) and not chk[nx][ny] and board[nx][ny] > height:
                chk[nx][ny] = True 
                dq.append((nx, ny))

res = 1 # 최댓값으로 업데이트

for height in range(1, 101): # N: 1~100까지 높이
    ans = 0 # 연결요소의 개수
    chk = [[False] * (N) for _ in range(N)]
    
    for i in range(N):
        for j in range(N):
            if not chk[i][j] and board[i][j] > height:
                ans += 1 
                bfs(i, j) # x, y
    
    res = max(res, ans)

print(res)