inflearn logo
강의

Khóa học

Chia sẻ kiến thức

Giới thiệu về giải bài toán bằng thuật toán Python (chuẩn bị cho bài kiểm tra viết mã)

14. Khu vực an toàn (DFS)

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

302

hyexxxmi5095

3 câu hỏi đã được viết

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))





 

python 코테 준비 같이 해요!

Câu trả lời 2

0

hyexxxmi5095

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

0

codingcamp

안녕하세요^^

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

기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.

1

112

2

스택에서 ')'을 만나는 경우

0

128

3

문제가 어디있나요?

0

100

2

변수 or 함수명

0

86

1

침몰하는 타이타닉 문제 질문입니다

0

78

1

AA.py 책점 에러

0

72

1

오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.

0

127

2

5.동전분배하기 문제 밑에코드도 정답이될까요?

0

124

1

아나그램 비교 코드

0

139

2

AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.

0

171

2

문제 링크가있나여?

0

157

2

채점기 Time Limit Exceeded 오류 문의

1

202

2

동적계획법은 사용하는 문제

0

140

2

제 코드 좀 봐주세요

0

161

1

예외가 존재할 가능성?

0

107

1

3번이 안풀립니다

0

102

0

5번 틀림

0

126

0

오류원인?

0

111

0

리스트 선언

0

129

1

침몰하는 타이타닉(그리디) 문제 질문

0

118

1

알고리즘

0

79

1

코딩테스트

0

106

1

DFS 순서 질문드립니다.

0

143

2

left, right를 사용한 풀이법에 대한 질문입니다

0

103

1