7576

날짜 : 2022. 10. 31

사용 언어 : python

 

문제

 

 

코드

 

import sys
from collections import deque

m, n = map(int, sys.stdin.readline().split()) # 가로, 세로
box = []
q = deque()
total = -1

dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]

def bfs():
    while q:
        t = q.popleft()
        for i in range(4):
            nx = t[0] + dx[i]
            ny = t[1] + dy[i]
            if nx in range(n) and ny in range(m) and box[nx][ny] == 0: # 안익은 경우
                q.append([nx, ny])
                box[nx][ny] = box[t[0]][t[1]] + 1 # 익은 날짜 설정
        """for i in range(n):
            print(box[i])
        print()"""
    return

# 토마토 입력
for i in range(n):
    box.append(list(map(int, sys.stdin.readline().split())))


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

bfs()
total = 0

for i in range(n):
    for j in range(m):
        if box[i][j] == 0:
            print(-1)
            exit(0)
        total = max(total, box[i][j])
print(total-1)

 

시간초과

import sys
from collections import deque

m, n = map(int, sys.stdin.readline().split()) # 가로, 세로
box = []
q = deque()
total = -1

def bfs(row, col):
    q.append([row, col, 1])
    dr = [0, 0, 1, -1]
    dc = [1, -1, 0, 0]
    while q:
        t = q.popleft()
        for i in range(4):
            r = t[0] + dr[i]
            c = t[1] + dc[i]
            day = t[2] + 1
            if c in range(m) and r in range(n):
                if box[r][c] == 1 or box[r][c] == -1:
                    continue
                elif box[r][c] == 0: # 안익은 경우
                    box[r][c] = day # 익은 날짜 설정
                    q.append([r, c, day])
                else: # 날짜를 체크한 경우
                    if day < box[r][c]: # 더 작은 값이 있을 경우
                        box[r][c] = day
                        q.append([r, c, day])
                    #box[i][j] = min(box[i][j], day)
        """for i in range(n):
            print(box[i])
        print()"""
    return

# 토마토 입력
for i in range(n):
    box.append(list(map(int, sys.stdin.readline().split())))


for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            bfs(i, j)
check = True
for i in range(n):
    for j in range(m):
        total = max(total, box[i][j])
        if box[i][j] == 0:
            check = False
            break

if not check:
    print(-1)
else:
    if total == 1: print(0)
    else: print(total-1)

 

알게된 점

- 한 3시간을 씨름한 문제였다.

- dfs를 활용해서 해결해야 하는 것에는 적절하게 접근했고 익은 날짜를 기록하면서 dfs를 전개하는것까지는 맞았다.

- 그러나 아래 코드에서 볼 수 있듯 맨 처음에 box의 값이 1인 경우 곧바로 bfs를 실행해서 시간을 낭비했고,

- 쓸데없이 조건을 넣어 추가로 enque하게 되어 시간을 낭비했다.

- 이후에 풀이를 찾아보니까 1을 발견할때마다 해당 좌표를 큐에 넣고 한번에 bfs를 돌리는 것이 이 풀이의 핵심이었다.

- 그렇게되면 겹쳐서 값을 수정할 일도 없고, 값은 1부터 오름차순으로 진행되기 때문에 자연스럽게 박스의 값이 0인 좌표는 저절로 증가해서 이상적인 결과가 나오기 때문이다.

- 그리고 결과를 출력하는 과정에서 이중 for문을 한번에 탈출하기 위해 exit(0)을 사용하는 것도 알게되었다.

- 막상 이렇게 풀이를 보니까 굉장히 간단간단하게 생각하고 푼거같은데 아직 공부할 게 많이 남았다는 생각이 든다.

 

 

참고 사이트

- https://jiwon-coding.tistory.com/97

[백준] 7576번 토마토 / 파이썬(python)