2468 - 파이썬

 

2468번: 안전 영역 (acmicpc.net)

2468번: 안전 영역

최근에 큰 비가 있었는데 어떻게 때를 맞춰서 풀어본 문제다.

문제의 포인트는 최대의 넓이를 갖는다는것이다.

즉 이말은 max_num 만큼 다 돌려주는게 포인트다.

 

---

내 풀이

from collections import deque
import sys

input = sys.stdin.readline


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

def solution(x,y,max):
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    q = deque([(x,y)])
    visitied[x][y]=1
    
    while q:
        a,b = q.popleft()
        for i in range(4):
            nx = dx[i] + a
            ny = dy[i] + b
            
            if 0 <=nx < N and 0 <=ny <N:
                if graph[nx][ny] > max and visitied[nx][ny]==0:
                    visitied[nx][ny]=1
                    q.append((nx,ny))

max_num = 0
result=0
for i in graph:
  for j in i:
    if max_num < j:
      max_num = j                
      
                    
for k in range(max_num):
    count=0
    visitied = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if graph[i][j] > k and visitied[i][j]==0:
                solution(i,j,k)
                count +=1
    if result < count :
        result = count
print(result)​

       

                   

                   

               

           

   

       

   

   

   

---

흔한 bfs다. 꽤 많이 풀다보니 이제는 진짜 많이 익숙해진 듯 하다. 

 

---

다른사람의 풀이

 

---

---

한동안 토이프로젝트 진행한다고 안올렸었는데 다시 열심히 해봐야 겠다.