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

🥚문제

---

🥚입력/출력

---

🍳코드

from collections import deque

# 데이터 받기
m, n = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(n)]

# 데이터 검증 함수
def box_check(box):
    # 1. 토마토가 전부 1이면 -> 0
    all_one = True
    for row in box:
        for tomato in row:
            if tomato != 1:
                all_one = False
                break
    if all_one:
        return 0
    # 2. 토마토 중 1이 없으면 -> -1
    no_one = True
    for row in box:
        for tomato in row:
            if tomato == 1:
                no_one = False
                break
    if no_one:
        return -1
    # 3. 둘 다 아니면 -> BFS 수행
    return 1

# BFS 함수
def bfs(box):
    queue = deque()
    # 1(익은 토마토) 찾기
    for x in range(n):
        for y in range(m):
            if box[x][y] == 1:
                queue.append((x, y))
    # 변수 설정
    day = 0
    while queue:
        now_x, now_y = queue.popleft()
        day = box[now_x][now_y]
        # 상, 하, 좌, 우
        x_movs = [-1, 1, 0, 0]
        y_movs = [0, 0, -1, 1]
        for i in range(4):
            next_x = now_x + x_movs[i]
            next_y = now_y + y_movs[i]
            if 0 <= next_x < n and 0 <= next_y < m:
                if box[next_x][next_y] == 0:
                    queue.append((next_x, next_y))
                    box[next_x][next_y] = day + 1 # 방문 표시
    # 우리는 첫 1에서부터 1씩 더해 날짜 수를 계산했으나, 첫 날은 0일째로 친다면 -1 필요
    return day-1

# 데이터 검증 함수 호출
check = box_check(box)
# 검증 결과 이상 없음
if check == 1:
    # BFS
    max_day = bfs(box)
    # max_day 출력 전, data 내에 0이 남아 있는지 확인한다.
    complete = True
    for row in box:
        for tomato in row:
            if tomato == 0:
                complete = False
                break
    if complete:
        print(max_day)
    # 익지 않은 토마토 남아 있을 때
    else:
        print(-1)
# 검증 결과 -1, 0
else:
    print(check)

---

🧂아이디어

• 새학기 시작과 함께 정보처리기사를 준비하느라 한 한 달 동안 손을 못 댔더니 확실히 감이 좀 떨어진 것 같다... 코드가 쓸데 없이 긴 느낌도 들고

• 모든 토마토가 익을 수 있는 최소 일 수를 계산하는 문제였다. BFS를 사용하여 문제를 해결했다.

• 이 때, 1(익은 토마토)를 기점으로 BFS를 탐색해 가는데, 상자 내에 1이 여러 개일 때는 동시다발적으로 BFS가 진행되어야 한다.

• 값이 1인 점을 인자로 넘겨 BFS 함수를 수행하는 형태가 아니라, box(data 전체)를 BFS 함수의 인자로 넘겨 처음에 1인 부분을 모두 queue에 넣고 시작하는 것이 맞는 방법이다.

• 따로 방문 표시를 하는 리스트는 만들지 않았다. 값이 0이면 아직 방문하지 않았다는 뜻이다.

• bfs함수 안에서 day라는 변수를 만들었다. day에는 탐색을 시작하는 지점에 저장된 현재 값을 할당한다.
  첫 날 1인 지점에서 다음날 익을 수 있는 토마토를 탐색하면, 이 때 day의 값은 1이 된다.
  1인 지점에서 탐색했을 때 다음날 익을 수 있다고 판단되는 토마토의 값은 day+1이 된다. 즉, 2가 된다.

• day를 계속 저장하고 있다가 return한다. 이때, 맨 처음 상태를 0일 뒤로 치므로 day-1을 해줘야 한다. (맨 처음 시작을 day=1로 하므로)

• 토마토가 익을 수 있는지 없는지, bfs 호출 후에는 아직 안 익은 토마토가 존재하는지를 지속적으로 체크해야 한다.