문제 출처 : https://www.acmicpc.net/problem/7576
사고과정
처음부터 조금 잘못생각하고 있었다.
구하고자 하는 것은 며칠 만에 모두 익는가? => 결과는 N일 OR -1
일수를 구하는 것은 최단 경로와 마찬가지이기 때문에 처음 있는 토마토들을 기본값으로 시작하여 BFS를 실행하면 되겠다 라고 생각했다. 이때 부차적으로 중복되는 값이나 방문여부 등에 대해서도 고려해야지. 이렇게 한다면 언제 종료되는가? 모든 가능한 0들이 1로 바뀔때 (상당히 추상적)
그런데 만약 0이 1로 바뀔수 없다면? => -1
이런 경우를 어떻게 처리해야 할까. 이런 상황을 코드로 작성하여 예외값 처리를 해두면 되겠지. 이런 상황을 코드로 작성하는 것을 고민하다 보니
1번. 모든 요소를 하나하나 조회한 뒤 DFS를 하여 0으로 갇힌 구역이 존재하는지 조사하자.
2번. 매 연산마다 1의 개수를 COUNT하는데 COUNT의 변화가 더 이상 생기지 않으면? 이제 변화될수 있는게 없음을 의미하므로 종료
1번은 상당히 너무 복잡해지고 시간도 커질 것 같아서 2번이 맞겠다 라고 생각했다.
그래서 일단 BFS로 코드를 작성해봤다. 코드를 작성하다 보니 만약 다음 요소가 0이라면 '익는다' 그렇지 않으면 그냥 넘어간다. 이렇게 보니 결국 BFS로 작성하면 "0"인 부분만을 체크하여 위와 같은 경우를 고려할 필요가 없었다. 애초에 내가 값을 변경하고자 하는 값만을 탐색하여 작동한다.
머릿속에 BFS과정과 이런 상황을 이해하고 숙련시키자.
import sys
from collections import deque
M,N = list(map(int,sys.stdin.readline().rstrip("\n").split()))
box = [list(map(int,sys.stdin.readline().rstrip("\n").split())) for _ in range(N)]
dic = [[-1,0],[0,1],[1,0],[0,-1]]
tomato = deque([])
time, cant, t_n = 0, 0 , 0
for j in range(M) :
for i in range(N) :
if box[i][j] == 1 :
tomato.append([i,j])
t_n+=1
elif box[i][j] == -1 :
cant+=1
n=len(tomato)
while tomato :
if n == 0 :
n=len(tomato)
time+=1
node = tomato.popleft()
n-=1
for i in range(4) :
nx = node[0]+dic[i][0]
ny = node[1]+dic[i][1]
if nx<0 or nx>N-1 or ny<0 or ny>M-1 :
continue
if box[nx][ny] == 0 :
t_n+=1
box[nx][ny] = 1
tomato.append([nx,ny])
if M*N-cant == t_n :
print(time)
else :
print("-1")시간이 다른 사람들에 비해 조금 오래 걸린다. 그리고 내 스스로 맘에 안 드는 부분도 있고. 조금 더 다듬어보자.
...가끔은 노가다가 더 빠르다는 게 약간 허무하다.
import sys
from collections import deque
M,N = list(map(int,sys.stdin.readline().rstrip("\n").split()))
box = [list(map(int,sys.stdin.readline().rstrip("\n").split())) for _ in range(N)]
dic = [[-1,0],[0,1],[1,0],[0,-1]]
tomato = deque([])
def bfs(M,N):
time = 0
for j in range(M) :
for i in range(N) :
if box[i][j] == 1 :
tomato.append([i,j])
n=len(tomato)
while tomato :
if n == 0 :
n=len(tomato)
time+=1
node = tomato.popleft()
n-=1
for i in range(4) :
nx = node[0]+dic[i][0]
ny = node[1]+dic[i][1]
if nx<0 or nx>N-1 or ny<0 or ny>M-1 :
continue
if box[nx][ny] == 0 :
box[nx][ny] = 1
tomato.append([nx,ny])
for j in range(M) :
for i in range(N) :
if box[i][j] == 0 :
print("-1")
return
print(time)
return
bfs(M,N)그냥 이중 for문을 이용하여 작성하였다. 심플하지만 숫자 연산이 더 빠를거라 생각해서 처음에는 숫자를 이용하였는데 결과는
약 700ms 정도 빠르다. 다른 사람은 좀 더 간단하고 짧게 했는데 마지막으로 참고하자. ( 왜 진짜 근데 단순하게 하는 게 더 빠른거지... )
메모리와 속도의 차이가 유의미하게 크다고 판단해 기록. 메모리는 거의 1.5배(50mb), 속도는 200ms정도 차이난다. 둘의 차이점은 불필요한 first 리스트. 실제 필요하지 않은 변수들의 사용으로 메모리가 증가할 수 있다. 그렇기 때문에 더 효율적으로 짜기 위해 불필요한 부분, 간결화 할 수 있는 부분이 있는지 고민해야 한다.
매개 변수를 리스트로 넘길려고 처음에 설정하다 보니 이 틀에 갖혀버렸다. 다시 말하지만 변수 사용은 DP와 같은 필요한 상황이 아니라면 삭제하고 간결화하자!
1.height를 노드의 개수로 계산하여 일일이 하지말자!
2. 리스트보다 튜플이 가볍고 빠르다! 가변적이지 않은 자료에 대해서는 튜플을 이용하자.
