[백준(BOJ)] 2468번 : 안전 영역 - PYTHON[파이썬]

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

2468번: 안전 영역

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 브루트포스 알고리즘
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

bfs코드를 먼저 짜준다. 그다음 rain이라는 변수를 설정해 입력받은 배열에서 가장 큰 높이까지 한 바퀴를 돌 때마다 값을 하나씩 올려준다.

 

그러다가 그 값이 가장 큰 높이까지 도달하면 bfs로 조사한 안전한 지역 중 최대를 출력해주면 된다.

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
arr = [list(map(int, input().strip().split())) for _ in range(N)]
visited = [[0]*N for _ in range(N)]

dx = [0,0,-1,1]
dy = [1,-1,0,0]
maxValue = max(map(max, arr))
result = 0
temp = 0
rain = 0
q = deque()

def bfs(x,y):
    global rain
    q.appendleft([x,y])
    visited[x][y]=1
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N and not visited[nx][ny]:
                if rain<arr[nx][ny]:
                    q.append([nx,ny])
                    visited[nx][ny]=1

while maxValue>rain:
    for i in range(N):
        for j in range(N):
            if visited[i][j]==0 and rain<arr[i][j]:
                bfs(i,j)
                temp+=1
    visited = [[0]*N for _ in range(N)]
    result = max(temp,result)
    temp = 0
    rain+=1

print(result)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!