• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

bfs로 풀어봤는데 답이 안 나옵니다.

21.02.08 22:28 작성 조회수 167

0

안녕하세요 문제를 bfs 방식으로 풀어봤는데 답이 1로 나옵니다. 코드를 살펴봐도 뭐가 잘못된건지 모르겠어서 질문남깁니다.

높이 범위가 1~100이여서 물에 잠기지 않는 영역에 방문시 0으로 바꾸는 식으로 풀어봤는데 아무래도 이 방식이 잘못된건가요?


import sys
from collections import deque
sys.stdin = open("input.txt", 'r')

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dq = deque()
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
area = []

for rain in range(1, 101):
    count = 0
    for i in range(n):
        for j in range(n):

            if board[i][j]>rain:
                board[i][j] = 0
                dq.append((i,j))
                while(dq):
                    tmp = dq.popleft()
                    for k in range(4):
                        x = tmp[0] + dx[k]
                        y = tmp[1] + dy[k]
                        if 0 <= x < n and 0 <= y < n and board[x][y] > rain :
                            board[x][y] = 0
                            dq.append((x,y))
                count += 1
    area.append(count)
  
print(max(area))





 

답변 2

·

답변을 작성해보세요.

0

김쪼며님의 프로필

김쪼며

질문자

2021.02.09

아..! 제가 왜 그 생각을 못했을까요..감사합니다!!

0

안녕하세요^^

board 를 0으로 바꾸어 체크를 하면 rain값이 2부터는 board상태가 어떤 상태인지 생각해보세요.