고슴도치의 queue만 사용하는 방법
문제 풀이 아이디어
- 최단 거리 문제이기 때문에 bfs를 사용해야 합니다.
- 하지만 1초 마다 지도의 상황이 바뀌므로 (물의 이동) bfs 도중에 1초가 지나면 지도를 업데이트한 후 bfs를 시행해야 합니다.
- queue에 위치를 넣을 때 시간을 같이 저장하고 pop 하다가 시간이 1초 지났다면 지도를 업데이트합니다.
코드
// 탈출
// 물의 위치를 기록할 튜플 자료형
typealias Position = (r: Int, c: Int, time: Int)
// 큐 구현
struct Queue {
var queue = [Position]()
var index = 0
var isEmpty: Bool {
return queue.count - index == 0 ? true : false
}
mutating func push(_ p: Position) {
queue.append(p)
}
mutating func pop() -> Position {
defer {
index += 1
}
return queue[index]
}
}
// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let R = input[0], C = input[1]
var matrix = [[Character]]()
for _ in 0..<R {
matrix.append(readLine()!.map{ $0 })
}
// 고슴도치가 방문한 곳 check
var check = Array(repeating: Array(repeating: false, count: C), count: R)
// 동서남북 이동 방향
let dr = [1, -1, 0, 0]
let dc = [0, 0, 1, -1]
// 유효한 좌표인지 확인
func isValid(_ r: Int, _ c: Int) -> Bool {
return r >= 0 && r < R && c >= 0 && c < C ? true : false
}
// 1초 후에 물이 있을 곳을 지도 상에 표시하는 함수 -> 지도 업데이트
func moveWater() {
// 한번 이동된 물에 대해서는 이동하지 않도록 check하기
var waterCheck = Array(repeating: Array(repeating: false, count: C), count: R)
// 지도 전체를 돌면서
for r in 0..<R {
for c in 0..<C {
// 한번 이동한 물이 아니라면
if matrix[r][c] == "*" && !waterCheck[r][c] {
for i in 0..<4 { //👉 동서남북 이동
let nr = r + dr[i]
let nc = c + dc[i]
if isValid(nr, nc) && matrix[nr][nc] == "." { //👉 물이 이동 가능한 곳이라면
matrix[nr][nc] = "*" // 지도에 표시
waterCheck[nr][nc] = true // 한번 이동된 물 체크
}
}
}
}
}
}
// bfs (시작점을 인자로 받음)
func bfs(_ start: Position) {
var queue = Queue()
// 시작점 push, 방문 체크, 현재 시간 저장
queue.push(start)
check[start.r][start.c] = true
var nowTime = start.time //👉 출발점에서는 0
// 일단 물 한번 이동한다. (1초 후에 물이 들어올 곳은 이동하지 못하므로)
moveWater()
while !queue.isEmpty {
let p = queue.pop()
// 현재 pop 이동장소의 시간이 현재 시간보다 크다면 (1초 더 지난 후에 이동하는 장소인 상황)
if nowTime < p.time {
nowTime = p.time
moveWater() //👉 1초 후에 물 들어올 곳은 미리 표시해두고 고슴도치 이동
}
// 동서남북으로 이동가능한지 확인
for i in 0..<4 {
let nr = p.r + dr[i]
let nc = p.c + dc[i]
if isValid(nr, nc) && !check[nr][nc] { // 이동 가능 및 방문 하지 않은 곳
if matrix[nr][nc] == "D" { //👉 목적지 도착
print(p.time + 1) //👉 현재 위치까지 걸린 시간에 + 1초해서 출력
return
} else if matrix[nr][nc] == "." { //👉 아무 것도 없어서 이동할 수 있는 장소
queue.push((r: nr, c: nc, time: p.time + 1)) //👉 현재 위치까지 걸린 시간에 + 1초해서 push
check[nr][nc] = true // 방문 check
}
}
}
}
print("KAKTUS")
}
// 출발점 찾아서 bfs 시작
for r in 0..<R {
for c in 0..<C {
if matrix[r][c] == "S" {
bfs((r: r, c: c, time: 0))
}
}
}⭐️ 고슴도치와 물의 queue 두 종류를 사용하는 방법
더 세련된 방법입니다.
문제 풀이 아이디어
# 사용해야 하는 알고리즘 = bfs
: 2개의 큐를 가지고 bfs를 실시합니다.
# 문제 풀이 아이디어
: 물 먼저 bfs하고
: 고슴도치가 나중에 bfs하면 합니다.
: 단, 1초씩 번갈아 가면서 해야 합니다! (큐 2개 사용)
# 의사코드
1. 입력 받기
2. 큐를 2종류 선언합니다. (고슴도치용, 물용)
3. "S"의 좌표를 고슴도치 큐에 넣고 "*"의 좌표를 물 큐에 넣습니다.
4. 두 큐를 이용해서 번갈아서 bfs를 실시하는데 1초씩 번갈아서 해야하므로
4-1. 큐에 추가할 때 바로 큐에 넣지 않고
4-2. 임시로 빈 큐에 넣어두었다가 큐가 비면 bfs를 종료하고
4-3. 임시 큐의 좌표를 큐에 옮기고 다른 bfs를 실시합니다.
5. bfs는 고슴도치 큐에 더 이상 추가될 좌표가 없을 때까지 실시합니다.
5-1. 고슴도치 큐에서 bfs를 하다가 "D"를 만나면
5-2. 현재 시간에서 + 1해서 출력하고 리턴합니다.
6. 고슴도치 큐가 빌 때까지 결과가 리턴 안되면 해당 문자열을 출력합니다.코드
// 탈출
// 물의 위치를 기록할 튜플 자료형
typealias Position = (r: Int, c: Int)
// 큐 구현
struct Queue {
var queue = [Position]()
var index = 0
var isEmpty: Bool {
return queue.count - index == 0 ? true : false
}
mutating func push(_ p: Position) {
queue.append(p)
}
mutating func pop() -> Position {
defer {
index += 1
}
return queue[index]
}
}
// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let R = input[0], C = input[1]
var matrix = [[Character]]()
for _ in 0..<R {
matrix.append(readLine()!.map{ $0 })
}
// 고슴도치가 방문한 곳 check
var check = Array(repeating: Array(repeating: false, count: C), count: R)
// 동서남북 이동 방향
let dr = [1, -1, 0, 0]
let dc = [0, 0, 1, -1]
// 유효한 좌표인지 확인
func isValid(_ r: Int, _ c: Int) -> Bool {
return r >= 0 && r < R && c >= 0 && c < C ? true : false
}
// 큐 2개 선언
var queue = Queue()
var waterQueue = Queue()
// bfs (시작점을 인자로 받음)
func bfs() {
var time = 0 //👉 현재 이동까지 걸린 시간
while !queue.isEmpty {
time += 1 //👉 시간 + 1
//⭐️ 임시 저장용 queue
var temp = Queue()
// 일단 물부터 이동 (물이 들어올 자리는 이동 불가이므로)
while !waterQueue.isEmpty {
let water = waterQueue.pop()
for i in 0..<4 {
let nr = water.r + dr[i]
let nc = water.c + dc[i]
// 물이 이동할 수 있는 자리라면
if isValid(nr, nc) && matrix[nr][nc] == "." {
matrix[nr][nc] = "*" //👉 지도에 물로 표시
temp.push((r: nr, c: nc)) //👉 임시 queue에 저장
}
}
}
// 임시 queue를 물 queue에 할당하고 임시 queue 비우기
waterQueue = temp
temp = Queue()
// 고슴도치 이동
while !queue.isEmpty {
let p = queue.pop()
for i in 0..<4 {
let nr = p.r + dr[i]
let nc = p.c + dc[i]
if isValid(nr, nc) && !check[nr][nc] {
if matrix[nr][nc] == "D" { //👉 목적지에 도착하면 시간 출력
print(time)
return
} else if matrix[nr][nc] == "." { //👉 이동 가능한 장소라면
temp.push((r: nr, c: nc)) // 임시 큐에 push 하고
check[nr][nc] = true // 방문 체크
}
}
}
}
// 임시 queue를 고슴도치 queue에 할당
queue = temp
}
print("KAKTUS")
}
// 지도를 돌면서 고슴도치의 시작점과 물의 위치 각각의 queue에 넣기
for r in 0..<R {
for c in 0..<C {
if matrix[r][c] == "S" {
queue.push((r: r, c: c))
} else if matrix[r][c] == "*" {
waterQueue.push((r: r, c: c))
}
}
}
// bfs 실시
bfs()
백과사전 보다 항해일지(혹은 표류일지)를 지향합니다.