문제 정보
https://www.acmicpc.net/problem/7576
문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
접근방법
1. BFS를 이용하자
여러가지 환경들(교수님의 문제분류, 주변 친구들의 이야기) 에 의해서 탐색을 이용한 문제라는것은 알았다.
최소 일수를 구하는 프로그램을 작성하라 라는 요구사항을 읽고 BFS를 이용하면 더 쉽게 풀 수 있을 것이라고 생각했다.
2. 델타를 이용하자
하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다.를 읽고
델타를 이용해서 탐색을 진행해야 할 것이라는 힌트를 얻을 수 있었다.
3. 필요한 일수를 계산하자
어떻게 하면 필요한 최소 일수를 계산할 수 있을까? 하루에 익을 수 있는 토마토가 전부 익은 후 하루를 끝내자
4. 익은 토마토가 하나 이상이라면?
문제의 핵심인 것 같았다. BFS를 이용하기로 했으니 deque를 사용하고 좌표를 어떻게 넣어줄지,
BFS를 어떻게 시작할지, 토마토가 있는 모든 좌표를 어떻게 탐색할지를 고민했다.
(설마 이건 아니겠지... 했던 방식이 정답이여서 허탈함을 느꼈다.)
1차 풀이(오답)
from collections import deque
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
def bfs():
cnt = -1
# visted[i][j] = 1
while Q:
for _ in range(len(Q)):
r, c = Q.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
#범위를 벗어나지 않고 옆이 0일때
if 0 <= nr < n and 0 <= nc < m and tomato[nr][nc] == 0:
tomato[nr][nc] = 1
Q.append((nr, nc))
cnt += 1
return cnt
m, n = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(n)]
# visted = [[0]*m for _ in range(n)]
Q = deque()
for i in range(n):
for j in range(m):
if tomato[i][j] == 1:
Q.append((i, j))
print(bfs())
1
처음에 BFS 함수의 r,c와 map을 통해서 받아오는 가로 세로값의 이름을 동일하게 해서
함수에 들어갔을때 매번 r, c 값이 변경되는 소소한 이슈가 있었다.
함수에서 사용되는 변수와 밖에서 사용되는 변수가 다르다고 생각해서 생긴 문제인데
이것 때문에 함수에 대해서 좀 더 공부해야 할 필요가 있다는게 더욱 와닿았다.
2
방문배열을 주석처리 한 것 처럼 처음에는 방문처리를 해주는 방식이 필요하다고 생각했다.
결론적으로 필요하지 않았고 기존 배열의 값을 변경시켜주는 방식으로 문제를 해결했다.
cnt 를 -1 로 설정해준 이유는 이미 익어있는 토마토를 기준으로 다음날이 시작되기 때문이다.
cnt를 0으로 설정해주면 요구한 출력값 보다 1 큰 수가 나타난다.
3
for _ in range(len(Q)): 를 통해서 덱에 들어있는 모든 좌표를 탐색할 수 있게 해주었다.
처음엔 너무 사람처럼 생각했다. 사람이 여러 방향을 탐색하기 위해서는 여러 사람이 필요하다(분신을 쓰든지)
하지만 컴퓨터의 경우는 반복을 하나의 반복문을 끝까지 수행하고 다음 단계로 넘어가기 때문에
일종의 분신술을 쓴 것과 같은 효과가 나타나서 문제를 해결할 수 있었다.
2차 풀이(오답)
from collections import deque
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
def bfs():
cnt = -1
# visted[i][j] = 1
while Q:
# 모두 익어있을 때
if len(Q) == (n*m):
return 0
# 모두 익지 않았을 때
else:
for _ in range(len(Q)):
r, c = Q.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
#범위를 벗어나지 않고 옆이 0일때
if 0 <= nr < n and 0 <= nc < m and tomato[nr][nc] == 0:
tomato[nr][nc] = 1
Q.append((nr, nc))
elif 0 <= nr < n and 0 <= nc < m and tomato[nr][nc] == -1:
return -1
cnt += 1
return cnt
m, n = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(n)]
# visted = [[0]*m for _ in range(n)]
Q = deque()
for i in range(n):
for j in range(m):
if tomato[i][j] == 1:
Q.append((i, j))
print(bfs())
신나서 바로 제출했다가 조건을 전부 만족하지 않았다는것을 알았다.
1. 모든 토마토가 익어있는 상태이면 0을 출력
2. 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
결론적으론 잘못됐지만 토마토가 전부 다 익어있는 아래와 같은 상황만 존재한다고 생각했다.
1 1
1 1
따라서 토마토가 전부 익은 상황 == 모든 상자에 토마토가 있는 상황(가로 * 세로) 라고 생각했고
if len(Q) == (n*m):
return 0
토마토가 있는 위치를 전부 덱에 넣어줬기 때문에 덱의 길이만큼 for 문을 전부 실행한 후 while문으로 돌아간다.
하지만 위의 1,2 조건에 대한 설정을 잘못 해 주었기 때문에 결과적으로 오답
3차 풀이(정답)
from collections import deque
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
def bfs():
global cnt
# visted[i][j] = 1
while Q:
# 모두 익어있을 때
# if len(Q) == (n*m):
# return 0
# 모두 익지 않았을 때
# else:
for _ in range(len(Q)):
r, c = Q.popleft()
for d in range(4):
nr = r + dr[d]
nc = c + dc[d]
#범위를 벗어나지 않고 옆이 0일때
if 0 <= nr < n and 0 <= nc < m and tomato[nr][nc] == 0:
tomato[nr][nc] = 1
Q.append((nr, nc))
cnt += 1
return cnt
m, n = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(n)]
# visted = [[0]*m for _ in range(n)]
Q = deque()
cnt = -1
for i in range(n):
for j in range(m):
if tomato[i][j] == 1:
Q.append((i, j))
bfs()
for i in range(n):
for j in range(m):
if tomato[i][j] == 0:
cnt = -1
break
if tomato[i][j] == 0:
break
print(cnt)
BFS 함수를 전부 수행하고 빠져나오게 되면 토마토 상자의 숫자는 전부 바뀌어져 있다고 생각했다.
따라서 함수 종료 이후에 for 문을 통해 배열을 전부 순회해 주었다.
만약 상자안에 0 이라는 숫자가 있다면 토마토가 익지 못했기 때문에 cnt 를 -1 으로 바꾸어 주었고
break를 두번 걸어서 전체 for문을 빠져나올 수 있게 해주었다.
토마토가 이미 전부 익어있는 경우에 대한 코드는 따로 생각해주지 않아도 괜찮았는데
그 이유는 토마토가 이미 익어있다면 Q에 전부 들어가 있는 상태일 것이고
for len(Q) 가 전부 끝난 이후에 +1 해주기 때문에 -1로 시작한 cnt는 0이 되고 함수를 빠져나오기 때문이다.
느낀점
1.
오늘은 교수님이 주신 코드를 전혀 참고하지 않고 기억에 의존해서 BFS 함수를 작성하였다.
완전히 같다고 할수는 없지만 기본적인 BFS 함수를 작성하는 방법이 조금 더 익숙해 진 것 같다.
2.
다른 과제가 너무 많아서 포기하고 스터디때 설명을 들으려 했다.
옆자리 친구가 스터디 원이여서 잡담을 하면서 내가 생각한 풀이를 이야기해주고 있는데
len(Q)를 사용해서 풀수있는게 맞다는 이야기를 듣고 문제풀이를 진행했다. 집에서 혼자 푸는 문제였으면
백프로 솔루션을 봤을텐데 이런 부분에서 싸피 네트워킹의 소중함을 느낀다.
3.
최근에 Django 수업을 시작하면서 생각치도 못한 백엔드에 재미를 붙히고 있는데
백엔드 개발자로 취업하기 위해선 알고리즘이나 자료구조가 많이 중요하다고 알고있다.
장고를 시작했다고 알고리즘에서 완전히 손을 떼지말고 꾸준하게 문제를 풀어야겠다.
아직 몇문제 안풀기도 했고
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 15649 N과 M (1) (파이썬) (0) | 2022.09.05 |
---|---|
백준 2667 단지번호붙이기(파이썬) (0) | 2022.09.04 |
백준 2477 참외밭(파이썬) (0) | 2022.08.25 |
SWEA 4875. [파이썬 S/W 문제해결 기본] 5일차 - 미로(파이썬) (0) | 2022.08.24 |
백준 2628 종이자르기(파이썬) (0) | 2022.08.21 |