728x90
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토
www.acmicpc.net
22/09/04
이 문제는 전형적인 BFS문제이고, 클래스에도 있는 전형적인 문제이다.
하지만 나는 이 문제에 대해서 특별한 추억을 가지고 있다.
때는 내가 BFS알고리즘을 배우지도 않은 PS 문제풀이 초반 시점에, 나는 호기롭게 이 문제에 도전했었다.
그냥 단순무식하게 깡 구현과 시뮬레이션으로 이 문제에 도전했었고, 당연히 실패했었다.
그리고 4달이 지난 후, BFS알고리즘을 배우고 나서 강해진 나는 이 문제를 한 번에 통과하고 말았다.
그때의 기분은 뭐라 설명할 수 없는 좋은 기분이였다.
첫 번째 접근 방식:
이 문제를 접근한 첫번째 방법을 소개하고자 한다.
말 그대로 깡으로 구현한 것이다.
근데 처음에 python으로 제출했더니 사간 초과가 나서 pypy로 제출했더니 인덱스 오류로 틀렸습니다를 받았다.
아마 구현 부분 중간에서 문제가 있는 것으로 생각이 되는데, 코드가 너무 길고 방대하여 고칠 엄두를 내지 못한 채로 오랜 시간이 지나가 버리고 말았다.
아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.
더보기
cols, rows = map(int, input().split())
tomato_mat = []
for _ in range(rows):
row = list(map(int, input().split()))
tomato_mat.append(row)
ripe_tomato_mat = []
for i in range(rows):
ripe_tomato_rows = []
for j in range(cols):
if tomato_mat[i][j] == -1:
ripe_tomato_rows.append(-1)
else:
ripe_tomato_rows.append(1)
ripe_tomato_mat.append(ripe_tomato_rows)
day = 0
if cols == 1 and rows == 1 and tomato_mat == [[0]]:
print(-1)
elif cols == 1:
while True:
if tomato_mat == ripe_tomato_mat:
print(day)
break
new_tomato_mat = []
for i in range(rows):
new_tomato_mat_rows = []
for j in range(cols):
if tomato_mat[i][j] == -1: # 비어있다면?
new_tomato_mat_rows.append(-1)
elif tomato_mat[i][j] == 1: # 당연히 익은곳은 그대로 일것.
new_tomato_mat_rows.append(1)
else: # 0인 경우에서 바뀔것이다???
if i == 0: # 왼쪽 위쪽 구석
if tomato_mat[i+1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
elif i == rows - 1: # 왼쪽 아래쪽 구석
if tomato_mat[i-1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
else: # 일반적인 경우
if tomato_mat[i-1][j] == 1 or tomato_mat[i+1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
new_tomato_mat.append(new_tomato_mat_rows)
if new_tomato_mat == tomato_mat: # 새로 만들었는데도 변화한 점이 없다면 더 이상 익지 못하는 상황임
print(-1)
break
tomato_mat = new_tomato_mat.copy() # 새로운 토마토 리스트 저장
day += 1
elif rows == 1:
while True:
if tomato_mat == ripe_tomato_mat:
print(day)
break
new_tomato_mat = []
for i in range(rows):
new_tomato_mat_rows = []
for j in range(cols):
if tomato_mat[i][j] == -1: # 비어있다면?
new_tomato_mat_rows.append(-1)
elif tomato_mat[i][j] == 1: # 당연히 익은곳은 그대로 일것.
new_tomato_mat_rows.append(1)
else: # 0인 경우에서 바뀔것이다???
if j == 0: # 왼쪽 위쪽 구석
if tomato_mat[i][j+1] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
if j == cols - 1: # 오른쪽 위쪽 구석
if tomato_mat[i][j-1] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
else: # 일반적인 경우
if tomato_mat[i][j+1] == 1 or tomato_mat[i][j-1] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
new_tomato_mat.append(new_tomato_mat_rows)
if new_tomato_mat == tomato_mat: # 새로 만들었는데도 변화한 점이 없다면 더 이상 익지 못하는 상황임
print(-1)
break
tomato_mat = new_tomato_mat.copy() # 새로운 토마토 리스트 저장
day += 1
else:
while True:
if tomato_mat == ripe_tomato_mat:
print(day)
break
# (code) # 새로운 토마토 행렬 만드는 과정
# 기본 경우, 벽에 있는 경우, 구석에 있는 경우를 모두 고려하여 코드를 짜보자
# 또한, 1*n 또는 n*1행렬 일때의 경우도 짜주자
new_tomato_mat = []
for i in range(rows):
new_tomato_mat_rows = []
for j in range(cols):
if tomato_mat[i][j] == -1: # 비어있다면?
new_tomato_mat_rows.append(-1)
elif tomato_mat[i][j] == 1: # 당연히 익은곳은 그대로 일것.
new_tomato_mat_rows.append(1)
else: # 0인 경우에서 바뀔것이다???
if i == 0:
if j == 0: # 왼쪽 위쪽 구석
if tomato_mat[i][j+1] == 1 or tomato_mat[i+1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
elif j == cols - 1: # 오른쪽 위쪽 구석
if tomato_mat[i][j-1] == 1 or tomato_mat[i+1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
else: # 위쪽 벽
if tomato_mat[i][j-1] == 1 or tomato_mat[i][j+1] == 1 or tomato_mat[i+1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
elif i == rows - 1:
if j == 0: # 왼쪽 아래쪽 구석
if tomato_mat[i][j+1] == 1 or tomato_mat[i-1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
elif j == rows - 1: # 오른쪽 아래쪽 구석
if tomato_mat[i][j-1] == 1 or tomato_mat[i-1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
else: # 아래쪽 벽
if tomato_mat[i][j-1] == 1 or tomato_mat[i][j+1] == 1 or tomato_mat[i-1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
elif j == 0: # 왼쪽 벽
if tomato_mat[i][j+1] == 1 or tomato_mat[i-1][j] == 1 or tomato_mat[i+1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
elif j == cols - 1: # 오른쪽 벽
if tomato_mat[i][j-1] == 1 or tomato_mat[i-1][j] == 1 or tomato_mat[i+1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
else: # 일반적인 경우
if tomato_mat[i][j-1] == 1 or tomato_mat[i][j+1] == 1 or tomato_mat[i-1][j] == 1 or tomato_mat[i+1][j] == 1:
new_tomato_mat_rows.append(1)
else:
new_tomato_mat_rows.append(0)
new_tomato_mat.append(new_tomato_mat_rows)
if new_tomato_mat == tomato_mat: # 새로 만들었는데도 변화한 점이 없다면 더 이상 익지 못하는 상황임
print(-1)
break
tomato_mat = new_tomato_mat.copy() # 새로운 토마토 리스트 저장
day += 1
두 번째 접근 방식:
이후 BFS알고리즘을 배운 후에는 이 방식으로 접근했다.
먼저 기존 그래프를 입력받은 후에 이를 변형시켜 빈 공간을 제외한 모든 토마토가 익어있는 그래프를 하나 만들었다.
그 이유는 이후에 기존 그래프에 DFS를 적용시켜 변형된 모습과 모든 토마토가 익어있는 그래프를 비교하여 실제로 모든 토마토가 익어있는지를 확인하기 위해서이다.
이후 BFS를 적용하는데, 노드를 큐에 추가할 때마다 시간이 1씩 늘어나는 것으로 설정했다.
또한 노드를 큐에 추가하는 조건은 아직 방문처리가 되지 않았고 그래프의 정상 범위 안에 있을 때를 기준으로 삼았다.
이후 큐를 돌 때마다 매번 최종 시간을 갱신하는데, 큐가 끝나면 그 시간을 반환하도록 만들었다.
이렇게 작성했더니 쉽게 맞았습니다를 받았다.
아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.
더보기
# 7576번 토마토
# 그래프 이론, 그래프 탐색, BFS
import sys
input = sys.stdin.readline
from collections import deque
C, R = map(int, input().rstrip().split())
graph = [list(map(int, input().rstrip().split())) for _ in range(R)]
compare = [[] for _ in range(R)]
for row in range(R):
for col in range(C):
if graph[row][col]:
compare[row].append(graph[row][col])
else:
compare[row].append(1)
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
def BFS():
queue = deque()
for row in range(R):
for col in range(C):
if graph[row][col] == 1:
queue.append((row, col, 0))
final_time = 0
while queue:
row, col, time = queue.popleft()
for r, c in zip(dr, dc):
nr, nc = row + r, col + c
if 0 <= nr < R and 0 <= nc < C and graph[nr][nc] == 0:
graph[nr][nc] = 1
queue.append((nr, nc, time+1))
final_time = time
return final_time
def main():
time = BFS()
for row in range(R):
for col in range(C):
if graph[row][col] != compare[row][col]:
print(-1)
return
else:
print(time)
main()'알고리즘 > 백준 문제 풀이' 카테고리의 다른 글
| [Python] 15645번 내려가기 2 (0) | 2022.09.21 |
|---|---|
| [Python] 4470번 줄번호 / 23803번 골뱅이 찍기 - ㄴ / 23804번 골뱅이 찍기 - ㄷ (0) | 2022.09.20 |
| [Python] 2381번 최대 거리 (0) | 2022.09.20 |
| [Python] 16456번 하와와 대학생쨩 하와이로 가는 거시와요~ (추후 보강 예정) (0) | 2022.09.19 |
| [Python] 16956번 늑대와 양 (0) | 2022.09.13 |
