[백준] 16197.두 동전 (Swift)

[백준] 16197.두 동전 (Swift)

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

16197번: 두 동전

풀이

주어진 2차원 배열 위에서 최단 거리를 찾아야 하니 BFS 로 해결할 수 있는 문제입니다. 다만 일반적인 BFS 문제와 조금 다른 점은 2개의 포인트가 동시에 같은 방향으로 움직인다는 것입니다.

 

움직이는 동전 2개 중 오직 1개만 보드 밖으로 나가게 되거나 움직이는 횟수가 10 보다 커지면 BFS 는 종료되어야 합니다. 동전이 보드를 탈출하지 못하는 경우는 BFS 함수가 종료되지 않고 끝까지 실행되는 경우이기 때문에 BFS 함수 끝 부분에 -1 을 출력해주면 됩니다.

 

저희가 고려해야 할 점들을 정리하자면,

• 동전 2개 중 오직 1개만 떨어지는 경우를 고려한다
• 움직이는 횟수가 10이 넘어가면 함수를 종료한다
• 동전 1개가 벽을 만나더라도 나머지 하나가 벽을 만나지 않는다면, 움직이는 횟수는 증가한다
• BFS 도중 함수가 종료되지 않고 끝까지 진행된다면, 보드를 탈출하지 못한 것으로 간주한다

정도로 볼 수 있습니다.

 

해당 조건들을 신경써서 코드를 작성한다면 문제를 해결할 수 있습니다.

코드

Swift

	import Foundation
	// MARK: - 선언
	// 좌표를 담을 구조체
	struct Point {
	var i: Int
	var j: Int
	var distance: Int
	}
	// 좌표 2개를 담는 구조체
	struct Coin {
	var A: Point
	var B: Point
	}
	func BFS() {
	var visited = Array(repeating: Array(repeating: false, count: m), count: n)
	var queue = DoubleStackQueue<Coin>()
	queue.enqueue(coins)
	visited[coins.A.i][coins.A.j] = true
	visited[coins.B.i][coins.B.j] = true
	while !queue.isEmpty {
	let now = queue.dequeue()!
	// 다음 이동이 10보다 커질 시 종료
	if now.A.distance >= 10 {
	print(-1)
	return
	}
	for i in 0 ..< 4 {
	let A = now.A
	let B = now.B
	// 코인 2개의 다음 좌표를 각각 정해줌
	let ai = A.i + di[i]
	let aj = A.j + dj[i]
	let bi = B.i + di[i]
	let bj = B.j + dj[i]
	// 만약 2개 다 보드 밖으로 나가는 경우라면 queue 에 추가하지 않음
	if !isInBound(ai, aj) && !isInBound(bi, bj) {
	continue
	}
	// A 코인이 나가는 경우, 거리 출력 후 종료
	if !isInBound(ai, aj) && isInBound(bi, bj) {
	print(A.distance + 1)
	return
	}
	// B 코인이 나가는 경우, 거리 출력 후 종료
	if isInBound(ai, aj) && !isInBound(bi, bj) {
	print(B.distance + 1)
	return
	}
	// a 가 벽을 만났을때
	if board[ai][aj] == 1 {
	// b 도 벽을 만났을때
	if board[bi][bj] == 1 {
	continue
	}
	// a 만 벽일때
	else {
	queue.enqueue(
	Coin(
	A: Point(i: A.i, j: A.j, distance: A.distance + 1),
	B: Point(i: bi, j: bj, distance: B.distance + 1)
	)
	)
	}
	}
	// b 가 벽을 만났을때
	else if board[bi][bj] == 1 {
	// a 도 벽을 만났을때
	if board[ai][aj] == 1 {
	continue
	}
	// b 만 벽일때
	else {
	queue.enqueue(
	Coin(
	A: Point(i: ai, j: aj, distance: A.distance + 1),
	B: Point(i: B.i, j: B.j, distance: B.distance + 1)
	)
	)
	}
	}
	// a,b 둘다 벽이 아닐때
	else {
	queue.enqueue(
	Coin(
	A: Point(i: ai, j: aj, distance: A.distance + 1),
	B: Point(i: bi, j: bj, distance: B.distance + 1)
	)
	)
	}
	}
	}
	// 여기까지 온다면 보드를 탈출하지 못했다는 뜻
	print(-1)
	}
	// 범위 바깥으로 나갔는지 검사
	func isInBound(_ i: Int, _ j: Int) -> Bool {
	return 0 <= i && i < n && 0 <= j && j < m
	}
	// MARK: - 실행
	let input = readLine()!.split(separator: " ").map { Int(String($0))! }
	let (n, m) = (input[0], input[1])
	var board = Array(repeating: Array(repeating: 0, count: m), count: n)
	var coinA: Point?
	var coinB: Point?
	// BFS 상하좌우 탐색을 위함
	let di = [1, -1, 0, 0]
	let dj = [0, 0, 1, -1]
	// 편의를 위해 board 를 Int 형 2차원배열로 바꿔주었음
	for i in 0 ..< n {
	let line = readLine()!.map { String($0) }
	for j in 0 ..< m {
	if line[j] == "#" {
	board[i][j] = 1
	} else if line[j] == "o" {
	if coinA == nil {
	coinA = Point(i: i, j: j, distance: 0)
	} else {
	coinB = Point(i: i, j: j, distance: 0)
	}
	}
	}
	}
	var coins = Coin(A: coinA!, B: coinB!)
	// BFS 함수 실행
	BFS()

view raw BOJ_16197.swift hosted with ❤ by GitHub