[BOJ] 2468번 안전 영역 / 사용언어 : 파이썬(python)

※ 문제링크

2468번: 안전 영역

해당 문제는 BFS를 활용해서 풀 수 있는 문제였다. 입력값중 최댓값을 구해서, 0부터 최댓값까지 BFS함수를 돌려서 안전 영역의 최대개수를 구하면 되었다. 자세한 문제풀이 방법과 코드는 아래와 같다.

1. 입력값을 바탕으로 2차원 배열을 만들고, 입력값을 받을 때마다 해당 리스트에서의 최댓값을 비교하여 배열 내 최댓값을 구한다.

2. 안전 영역의 범위를 탐색할 BFS함수를 작성하고, 방문기록을 확인할 방문기록 리스트를 만들어 준다.

3. 3중반복문을 통해 0  ~ 최댓값까지 수면한계치별로 안전영역의 최댓값을 구하고 리스트에 저장해준다.

4. 모든 입력값이 0일 경우와 그렇지 않을 경우를 고려하여 결과값을 출력해준다.

+ 시간 및 메모리 단축을 위해 sys를 사용하였다.(개행문자에 유의하자)

 

def bfs(x, y, limit):
    queue = deque()
    queue.append([x,y])
    visited[y][x] = True

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if visited[ny][nx] == False:
                    if field[ny][nx] > limit:
                        visited[ny][nx] = True
                        queue.append([nx, ny])
                    if field[ny][nx] <= limit:
                        visited[ny][nx] = True

import sys
from collections import deque

# input = sys.stdin.readline
N = int(input())
field = []
value = 0
for _ in range(N):
    K = list(map(int, input().split()))
    field.append(K)
    T = max(K)
    if value < T:
        value = T

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

ans_list = []
for i in range(value):
    visited = [[False for _ in range(N)] for _ in range(N)]
    cnt = 0
    for x1 in range(N):
        for y1 in range(N):
            if visited[y1][x1] == False:
                if field[y1][x1] <= i:
                    visited[y1][x1] = True
                if field[y1][x1] > i:
                    bfs(x1, y1, i)
                    cnt += 1
    ans_list.append(cnt)

if T == 0:
    print(0)
else:
    print(max(ans_list))

 

P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.