[Python][백준/BOJ] 2468번 : 안전 영역

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

2468번: 안전 영역

 

내 코드

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
maxi = max(map(max, graph))
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs(a,b, k):
    q = deque()
    q.append((a,b))
    visited[a][b] =1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<=nx < n and 0<= ny < n:
                if not visited[nx][ny] and graph[nx][ny] > k:
                    visited[nx][ny] =1
                    q.append((nx, ny))

ans =0
for k in range(maxi):
    visited = [[False]*n for _ in range(n)]
    cnt =0
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and graph[i][j] > k:
                cnt+=1
                bfs(i,j,k)
    ans = max(ans, cnt)

print(ans)

 

코드 리뷰

BFS

이 문제는 bfs를 준비하고 있는 사람이라면 풀어보면 좋을 문제라고 생각한다. 물론 백준 유저라면 풀어본 사람이 많겠지만 말이다. 다른 bfs보다 살짝 더 생각할 수 있는 문제이기 때문에 가볍게 풀어보기 좋다. 그리고 내가 DFS가 아니라 BFS로 푼 이유는 다름이 아니라 내가 그저 BFS를 더 선호하기 때문이다.. DFS로 풀어도 풀리긴 한다.

 

이 문제는 문제 자체를 이해하는 것이 중요하다. 높이가 다양하게 이루어진 배열이 주어진다. 그리고 높이를 바꿔가면서 최대로 물이 고이지 않는 높이를 구하는 것이 필요하다. 그러므로 높이를 조절하는 코드가 추가적으로 필요하다.

 

def bfs(a,b, k):
    q = deque()
    q.append((a,b))
    visited[a][b] =1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<=nx < n and 0<= ny < n:
                if not visited[nx][ny] and graph[nx][ny] > k:
                    visited[nx][ny] =1
                    q.append((nx, ny))

이 코드에서 주목할 점은 다음 좌표가 k보다 커야 한다는 조건문이다. k보다 큰 것만 물에 안 잠기니까, k를 받아와서 여기서 써먹어야 한다.

 

이건 전체적인 BFS 코드와 비슷하다. 다른 부분이라면 k가 추가적으로 사용된다는 점이다. 이 k의 정체는 밑의 코드에서 찾아볼 수 있다.

for k in range(maxi):
    visited = [[False]*n for _ in range(n)]
    cnt =0
    for i in range(n):
        for j in range(n):
            if not visited[i][j] and graph[i][j] > k:
                cnt+=1
                bfs(i,j,k)
    ans = max(ans, cnt)

k는 그래프에 존재하는 모든 숫자들이다. 1부터 가장 큰 수까지. 만약 그래프에 9까지 존재한다면 1부터 9까지 k로 여기고 돌려본다. 그래서 만약 조건에 부합하다면 거기부터 스타트해서 한바퀴를 돌고 count를 세면 된다. 간단하지만 조금 변형한 문제였다.