티스토리 뷰
포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.
문제를 보자.
문제가 길다.
이 문제를 보고 전에 풀었던 미로 문제와 유사하다고 느꼈다.
하지만 문제가 있다.
토마토가 두 개가 존재하는 경우인데, 이 경우 때문에 bfs로 안 풀릴 거라 생각했었다.
결과적으로 bfs문제이다.
코드
from collections import deque
n, m = map(int,input().split())
array = []
max_val = 0
queue= deque()
for i in range(m):
array.append(list(map(int,input().split())))
# print(array[i],end='\n') # 처음입력된 배열
if 1 in array[i]:
queue.append((i,array[i].index(max(array[i]))))
dx = [1,-1,0,0]
dy = [0,0,-1,1]
def bfs():
while queue:
y,x = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and array[ny][nx] == 0:
queue.append((ny,nx))
array[ny][nx] = array[y][x] + 1
bfs()
for i in range(m):
# print(array[i],end='\n') # 토마토 익은 후 배열
for j in range(n):
if array[i][j] > max_val :
max_val = array[i][j]
elif array[i][j] == 0:
max_val = 0
break
if max_val == 0:
break
print(max_val-1)
하지만 이 코드는 정답이 아니다.
근데 왜 정답이 아닌지 모르겠다...
진짜 모르겠다
추후에 이유를 알게 되었을 때 추가해서 포스팅 하겠다.
배운 점
1. 토마토가 두 개일 경우에도, 큐에 순서대로 넣어주면 정상적인 탐색이 진행된다.
'백준' 카테고리의 다른 글
백준 2667 문제풀이 [python] (0) | 2023.06.19 |
---|---|
백준 2751번 문제풀이 [python] (0) | 2023.06.19 |
백준 15552번 문제풀이 [python] (0) | 2023.06.18 |
백준 2309 문제풀이 [python] (0) | 2023.06.17 |
백준 2609 문제풀이 [python] (0) | 2023.06.17 |
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 상속
- java
- 백준
- 김영한 실전 자바 중급
- 프로그래머스 상품을 구매한 회원 비율 구하기
- 프로그래머스
- 백준 피보나치 수열
- 프로그래머스 상품을 구매한 회원 비율 구하기 파이썬
- Los
- 코딩테스트 준비
- 김영한 실전 자바 기본
- 백준 피보나치
- spring
- 기술스택
- webhacking.kr
- 스프링
- samron
- samron3
- 코딩테스트
- zixem
- extends
- 김영한 실전 자바 기초
- static
- 김영한
- 상품을 구매한 회원 비율 구하기 파이썬
- los 15
- los 15단계
- lord of sql
- ys.k
- 자바
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함
250x250