-
7569. [Python]토마토Python_알고리즘/Gold V 2024. 4. 25. 01:47
1. 문제
https://www.acmicpc.net/problem/7569
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 256MB
- 그래프 탐색
3. 파이썬 코드
import sys from collections import deque input = sys.stdin.readline N, M, H = map(int,input().split()) tomato = [ list(map(int,input().split())) for _ in range(M*H) ] direction = [(-1,0), (0,1), (1,0), (0,-1)] tomato_list = deque([]) # 일수 체크 day = 0 # 0의 개수 체크 zero_cnt = 0 # 익은 토마토 위치와 익지않은 토마토 개수 체크 for i in range(M*H): for j in range(N): if tomato[i][j] == 1: tomato_list.append((i,j)) elif tomato[i][j] == 0: zero_cnt += 1 # 익지 않은 토마토가 없는 경우 바로 종료 if zero_cnt == 0: print(0) exit() # 몇번 반복할지 몰라서 계속 반복 while True: # 임시 저장할 리스트 check_list = deque([]) # 토마토 위치가 없을때까지 반복 while tomato_list: check = tomato_list.popleft() # 고른 토마토 위치가 몇번째 높이인지 체크 range_check = check[0] // M # 방향배열 탐색 for k in range(4): ny = direction[k][0] + check[0] nx = direction[k][1] + check[1] # 범위 내에 존재할 경우 if (0 <= ny < M*H) and (0 <= nx < N): # 현재 고른 위치 내에서만 탐색 if range_check * M <= ny < (range_check + 1) * M: # 익지않은 토마토인 경우 토마토 익히고 개수 -1 후 위치 추가 if tomato[ny][nx] == 0: tomato[ny][nx] = 1 zero_cnt -= 1 check_list.append((ny,nx)) # 현재 뽑은 위치에서 위아래 층 도 익힘 nh = check[0] + M nmh = check[0] - M if 0 <= nh < M*H: if tomato[nh][check[1]] == 0: tomato[nh][check[1]] = 1 zero_cnt -= 1 check_list.append((nh,check[1])) if 0 <= nmh < M*H: if tomato[nmh][check[1]] == 0: tomato[nmh][check[1]] = 1 zero_cnt -= 1 check_list.append((nmh,check[1])) # 더이상 토마토를 체크할 수 없을 때 반복문 탈출 if not check_list and not tomato_list: break # 외의 경우 임시 저장한 리스트를 토마토 리스트에 추가 후 하루가 지남 else: tomato_list = check_list day += 1 # 만약 반복문이 끝난 후 토마토가 익지않은 것이 있을 경우 -1 출력 if zero_cnt == 0: print(day) else: print(-1)
4. 문제를 풀고난 후 생각
- 기존의 토마토와 비슷한 문제지만 층이 나뉘어 진 다른 문제이다.
- 2차원 배열 형태로 풀었고, 현재 위치가 몇층에 있는지를 확인한 후 그 층내에서 방향배열을 탐색하는 식으로 진행했다.
- 이후 층 위아래 칸에 토마토가 있어도 익어갈 수 있도록 BFS를 돌려주었고, BFS 외부에 while 문을 처리하여 몇번 시행할지 모르는 반복문을 돌려줬다.
- 리스트 두개가 비어있고, 익지 않은 토마토가 있는 경우 -1을 외의 경우 day를 출력해주는 방식으로 풀었다.
5. 문제를 푸는데 도움이 되는 지식
- 그래프 탐색
- 그래프 이론
'Python_알고리즘 > Gold V' 카테고리의 다른 글
13549. [Python]숨바꼭질 3 (0) 2024.05.22 14284. [Python]간선 이어가기 2 (0) 2024.05.08 7682. [Python]틱택토 (0) 2024.04.17 1456. [Python]거의 소수 (0) 2024.04.14 1916. [Python]최소비용 구하기 (1) 2024.03.05