Bibbidi Bobbidi Boo

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기


Greedy

4 / 50

 

탐색

4 / 50

 

기초 동적 프로그래밍

5 / 50(NEW!)

 

투포인터

0 / 10


1. 문제

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

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,

www.acmicpc.net

→ solved.ac 기준 골드 5

→ class 3


2. 문제 해결 아이디어

토마토를 보관하는 큰 창고 == graph

며칠이 지나면 토마토가 모두 익는가?에 대한 최소 일수 ⇒ 그래프 탐색

 

익은 토마토는 1, 익지 않은 토마토는 0, 안 들어 있으면 -1

탐색해나가면서 칸마다 며칠인지 더해주고,

마지막에 0이 있는지 확인 후 있으면 -1을 출력(토마토가 모두 익지는 못하는 상황).

없으면 가장 최대값을 출력한다.

 

어떻게 탐색하는가 ? BFS? DFS?

→ 처음에 DFS로 접근하려다가 작렬하게 실패... 

→ 해당 문제는 BFS 문제였음..

 

→ for문으로 graph에 접근하여 익은 토마토일 때 bfs 수행

queue에서 안 익은 토마토일 때 방문해서 경로를 기록한다.

→ 틀렸습니다

if, 그럼 만약 익은 토마토의 위치가 각각 x와 y에 있고, x < y라고 할 때

안 익은 z가 y에 더 가깝다.

이렇게 됐을 경우 먼저 x가 bfs를 수행하고 나서 y가 수행되므로 z가 전혀 반영 X. 실제로는 y가 수행되었을 때 반영되어야 한다.

→ 어떻게 x와 y 각각 수행하고 나서 최단 경로만 넣어두지??

→ 첫 번째 시도: 거리를 비교해서 늘 짧은 거리만 넣어둔다.

이렇게 구현했을 때 시간 초과 발생

→ 두 번째 시도: distance와 visited 도입해서 안 익은 토마토이면서 처음 방문했을 때만 최단 거리 기록

이렇게 구현했을 때 역시나 시간 초과 발생

 

2.1. 최종 아이디어.txt

처음 Queue에 방문이 필요한 노드(== 처음 익은 토마토)를 넣어두고 BFS를 수행

세 번째 시도: 아에 발상 전환, queue에 방문이 필요한 노드를 넣어두고 bfs를 수행

여기서 첫 방문이 필요한 노드는 결국 익은 토마토들.

익은 토마토들을 Queue에 넣어두고 차례로 빼면서 탐색을 수행하면

현재 Queue에 있는 노드와 가까운 것부터 수행되기 때문에 늘 최단 경로만 담게 된다


3. 구현

3.1. 내 풀이

<python />
from collections import deque import sys input = sys.stdin.readline # BFS 메서드 정의 def bfs(): # 큐가 빌 때까지 반복 while queue: # 큐에서 하나의 원소를 뽑아 출력하기 x, y, z = queue.popleft() # 인접한 원소(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)를 큐에 삽입 for i in range(6): nx = x + dx[i] ny = y + dy[i] nz = z + dz[i] if nx < 0 or nx >= h or ny < 0 or ny >= n or nz < 0 or nz >= m: continue # 안 익은 토마토이면서 처음 방문하는 경우에만 최단 거리 기록 if graph[nx][ny][nz] == 0 and not visited[nx][ny][nz]: queue.append((nx, ny, nz)) visited[nx][ny][nz] = True graph[nx][ny][nz] = graph[x][y][z] + 1 def solution(): tmp = True for i in range(h): for j in range(n): if 0 in graph[i][j]: tmp = False if tmp: return 0 for i in range(h): for j in range(n): for k in range(m): if graph[i][j][k] == 1: queue.append((i, j, k)) bfs() answer = -1 for i in range(h): for j in range(n): if 0 in graph[i][j]: return -1 answer = max(answer, max(graph[i][j])) return answer - 1 m, n, h = map(int, input().split()) graph = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)] visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(h)] queue = deque() dx = [1, -1, 0, 0, 0, 0] dy = [0, 0, 1, -1, 0, 0] dz = [0, 0, 0, 0, 1, -1] print(solution())

4. 메모

  • 걸린 시간: 2시간 이상..??
    • 예외는 금방 알아챘는데 시간 초과 안 나는 방법을 몰라서 2시간 이상 소요됨.. 
    • 답 보고 나서 며칠 지난 후 다시 풀었다.
  • 같은 이름의 토마토라는 문제가 있음.
    • 3차원 배열과 다르게 얘는 2차원 배열.
    • 문제 풀이 방식은 아마 같을 걸로 예상되나 직접 테스트하기에는 훨씬 덜 부담됨.
    • 이거 먼저 풀 걸......

5. 마치며

같은 문제지만 토마토 문제도 복습하는 의미에서 나중에 풀어봐야겠다.

어쨌든 첫트에 못 푼 문제이므로 ㅠㅠ(눈물 좔좔...)

 

 

profile

Bibbidi Bobbidi Boo

@비비디

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!