[Python] 백준 7576번 - 토마토

문제 https://www.acmicpc.net/problem/7576

7576번: 토마토

 

모각코에서도 얘기했듯이 이번 문제는 m, n을 구별하는 게 어려웠다.. 선형대수학 공부해야되나봐... row, col 왜 이리 헷갈리지.. 어제 스터디 할 때 관련 얘기 해서 row랑 col에 대해서 10분 동안 토의했는데 꼭 잘 기억해야지..

 

이 문제는 모각코 Today I Learned에서 이미 리뷰를 했기 때문에 조금만 더 덧대려고 한다.

2021.07.22 - [HUFS/HUFS 모각코 캠프] - [모각코] 210721 Today I Learned

 

 

1.

다른 bfs 문제들이랑 별반 다를 바 없었지만 여기서 조금 달랐던 점은 q.popleft() 하기 전에 for문을 넣어준 것이다.

모각코 글 쓸 때 for i in range(len(q)): 이 부분에 대한 설명이 잘못된 것 같다.

모각코 글에서는 '익은 토마토 주위에 있는 안 익은 토마토들을 하나하나 다 큐에 넣고 빼고 해주어야 하므로 for문을 사용했다.' 라고 했는데

다시 생각해보니 for문을 돌리는 이유는 익은 토마토가 여러 개인 경우를 생각해주어야 하기 때문이었다.

하루가 지나면 익은 토마토 주위의 안 익은 토마토들이 익게 되는데 상자에 익은 토마토가 여러 개 있는 경우 q에 집어넣은 후 한 번에 다 for문을 돌려서 처리를 해준 후, 다음 날로 넘어가야 한다. 

 

따라서 for문이 적용되는 원리가 '익은 토마토 주위에 안 익은 토마토가 여러 개 있어서' 가 아니라 (모각코에서의 설명) '하루에 익은 토마토가 여러 개 있을 수도 있어서' 정도로 설명할 수 있을 것 같다.

 

 

2.

문제 다 풀고 난 후 예외 처리할 때 예외의 조건을 쉽게 생각하는 연습을 하자.

아직 경험이 부족해서 쉬운 코드도 어렵게 돌아가는 경향이 있다. 내 코드가 뭔가 복잡하고 분명 이것보다 더 쉬운 길이 있을 거라는 생각이 조금이라도 들면 좀 더 간단하게 해결할 수 있는 방법을 생각해보자.

 

 

3.

q = deque()
    for i in range(n):
        for j in range(m):
            if tomato[i][j] == 1:
                q.append((i, j))

이 부분을 모각코 할 때는 bfs 함수 외부에서 미리 해 준 다음 bfs 함수를 호출했는데 다른 bfs 함수들이랑 다를 바가 없어서 다시 bfs 함수 내부에 넣어준 후 한 번 더 제출을 해보았다.

bfs 함수를 돌릴 때마다 큐 설정을 한 번 씩 더 해주어야 하는 거라서 시간 복잡도가 늘어나려나 했는데 오히려 줄었다... 이유는 모르겠다...

 

 

3번 부분의 위치를 바꿔준 것 빼고는 모각코 때 한 코드랑 다를 바 없지만 비교를 쉽게 하기 위해서 모각코 때 한 코드도 첨부한다.

 

 

#모각코 

import sys
from collections import deque

def bfs(v_row, v_col):
    count = 0
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        count += 1
        for i in range(len(q)):
            v_row, v_col = q.popleft()
            for row_move, col_move in move:
                row = v_row + row_move #v_row: 이동 전 값. row: 이동 후 값
                col = v_col + col_move
                if 0 <= row < n and 0 <= col < m and tomato[row][col] == 0:
                    tomato[row][col] = 1
                    q.append((row, col))
    
    for i in tomato:
        if 0 in i: #다 익지는 못하는 경우
            return -1
    return count - 1 #처음에는 count 안 하므로 빼줘야 함

m, n = map(int, sys.stdin.readline().split())
tomato = [0 for i in range(n)]
for i in range(n):
    tomato[i] = list(map(int, sys.stdin.readline().split()))

q = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            q.append((i, j))

print(bfs(n, m))

 

 

 

#deque 초기 선언을 bfs 함수 내부에서

import sys
from collections import deque

def bfs(v_row, v_col):
    count = 0
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    q = deque()
    for i in range(n):
        for j in range(m):
            if tomato[i][j] == 1:
                q.append((i, j))

    while q:
        count += 1
        for i in range(len(q)):
            v_row, v_col = q.popleft()
            for row_move, col_move in move:
                row = v_row + row_move #v_row: 이동 전 값. row: 이동 후 값
                col = v_col + col_move
                if 0 <= row < n and 0 <= col < m and tomato[row][col] == 0:
                    tomato[row][col] = 1
                    q.append((row, col))
    
    for i in tomato:
        if 0 in i: #다 익지는 못하는 경우
            return -1
    return count - 1 #처음에는 count 안 하므로 빼줘야 함

m, n = map(int, sys.stdin.readline().split())
tomato = [0 for i in range(n)]
for i in range(n):
    tomato[i] = list(map(int, sys.stdin.readline().split()))

print(bfs(n, m))

 

위에 있는 결과가 deque 초기 설정을 bfs 함수 내부에서 해준 것.

아래가 bfs 함수 외부에서 해준 것.

 

... 시간 복잡도 이해 안 가는데 일단 맞았으니까 넘어간다. !

 

 

 

---

 

 

#220130

 

확실히 예전보다는 문제 접근법이 쉽게 떠오른다.

90% 대에서 틀려서 예전에 맞은 코드를 참고했다.

return 해줄 때 인덴트를 잘못 넣어주어 그런 것 같다.

#이렇게 넣어야 하는데
for i in visited:
	if 0 in i:
		return -1
return max(map(max, visited)) - 1


#이렇게 함
for i in visited:
	if 0 in i:
		return -1
	else:
		return max(map(max, visited)) - 1

 

이거 해결했더니 잘 풀린다.. 

다른 부분에도 문제가 있었는지, 이 부분만 문제가 있었던 건지 궁금해서 visited 배열을 사용한 버전과 사용하지 않은 버전 둘 다 제출해보았다.

이 부분만 문제였다.

 

 

#visited 배열 사용 X (tomato 배열에 직접 +1)

import sys
from collections import deque
input = sys.stdin.readline

def bfs(y, x):
    dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        y, x = q.popleft()
        for dy, dx in dxdy:
            nx = x + dx
            ny = y + dy
            if -1 < nx < m and -1 < ny < n:
                if tomato[ny][nx] == 0:
                    tomato[ny][nx] = tomato[y][x] + 1
                    q.append((ny, nx))
        
    for i in tomato:
        if 0 in i:
            return -1
    return max(map(max, tomato)) - 1

m,n = map(int, input().split()) #m: 가로, n:세로
tomato = []
q = deque()
for _ in range(n):
    tomato.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            q.append((i, j))

print(bfs(n, m))

 

 

#visited 배열 사용

import sys
from collections import deque
input = sys.stdin.readline

def bfs(y, x):
    while q:
        y, x = q.popleft()
        dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dy, dx in dxdy:
            nx = x + dx
            ny = y + dy
            if -1 < nx < m and -1 < ny < n:
                if tomato[ny][nx] == 0 and not visited[ny][nx]:
                    q.append((ny, nx))
                    visited[ny][nx] = visited[y][x] + 1
        
    for i in visited:
        if 0 in i:
            return -1
    return max(map(max, visited)) - 1

m,n = map(int, input().split()) #m: 가로, n:세로
tomato = []
visited = [[0 for _ in range(m)] for _ in range(n)]
q = deque()
for _ in range(n):
    tomato.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            q.append((i, j))
            visited[i][j] = 1
        if tomato[i][j] == -1:
            visited[i][j] = 1

print(bfs(n, m))

 

당연히 visited 사용하지 않은 게 메모리, 시간 면에서도 효율적이다.