알고리즘) 백준 7569번 토마토 Swift

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

7569번: 토마토

---

예제

입력	출력
5 3 1 0 -1 0 0 0 -1 -1 0 1 1 0 0 0 1 1	-1
5 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0	4
4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 1 1 1 -1	0

 

---

문제 접근

이 문제는 3차원 배열이기 때문에 2차원 배열의 토마토 문제를 먼저 풀어 보는 것을 추천합니다.

먼저 토마토의 상태를 누적 방문 횟수라고 생각하며 접근했습니다. 방문하면(익으면) 누적 방문 횟수(익은 날짜)를 넣어 보았습니다.

• 1 = 익음 = 방문함
• 0 = 안익음 = 방문 안함
• -1  = 없음 = 방문할 수 없음

토마토가 인접한 곳을 두번째 예제를 이용해 도식화해보았습니다.
(박스 번호, 세로, 가로) 순서로 토마토가 익은 1의 위치를 3차원 배열로 표현하면 (1, 1, 2) 입니다.
위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향이 인접해 있으므로
기준점으로부터 (1, 0, 0), (-1, 0, 0), (0, 0, -1), (0, 0, 1), (0, -1, 0), (0, 1, 0) 만큼 떨어져 있습니다.

처음에 토마토가 익은 곳의 위치를 큐에 넣고 방문한 적 없는 인접한 토마토의 위치를 차례로 큐에 넣습니다.
큐에 있는 모든 토마토의 위치를 방문한 뒤 결과를 출력합니다.

• 안익은 토마토가 있으면 = 0인 값이 남아있으면 -1을 출력
• 처음부터 모두 익어있었으면 = 누적 방문 횟수 값이 1이면 = 0을 출력
• 익는데 며칠 지났다면 최대 누적 방문 횟수 값에서 초기화 값인 1을 빼고 출력
  
  

풀이

	func tomatobox() {
	let nums = readLine()!.split(separator: " ").map { Int($0)! }
	let m = nums[0], n = nums[1]
	var box = [[Int]]()
	var queue = [(Int, Int)]()
	var tomato = (0,0)
	for i in 0..<n {
	let values = readLine()!.split(separator: " ").map { Int($0)! }
	queue.append(contentsOf: values.enumerated().filter({ 1 == $0.element }).map { (i,$0.offset) }) // 값이 1인 indexes
	box.append(values)
	}
	var index = 0
	while(queue.count > index) {
	tomato = queue[index]
	for (i, j) in [(1, 0), (0, 1), (-1, 0), (0, -1)] {
	if (0..<n).contains(tomato.0+i), (0..<m).contains(tomato.1+j), // 범위 체크
	box[tomato.0+i][tomato.1+j] == 0 {
	queue.append((tomato.0+i, tomato.1+j))
	box[tomato.0+i][tomato.1+j] = box[tomato.0][tomato.1] + 1
	}
	}
	index += 1
	}
	let flatvisited = box.flatMap { $0 }
	let maxValue = flatvisited.max() ?? 1
	if flatvisited.contains(0) {
	print("-1")
	} else if maxValue == 1 {
	print("0")
	} else {
	print(maxValue-1)
	}
	}

view raw 백준 7569 토마토.swift hosted with ❤ by GitHub

 

풀이 속 출력 테스트 주석을 해제하여 실행해보면 이해가 빠르게 됩니다. 😊