문제 설명
- 일반적인 미로찾기인데 레버가 포함된 버전
- 레버를 꼭 지나가야 할 것
문제 접근
- 출발지에서 레버까지 최단
- 레버에서 출구까지 최단 더해주면 될 듯 ?
근데 그러면 방문한 곳을 또 방문할 수도 있는데 어쩌지 생각을 하다가..
레버까지 도착을 하고, 다시 방문배열을 초기화해주는 느낌으로 해주면 되겠다 싶었다.
문제풀이
- 일단 1차월 배열로 주어지는 지도를 2차원 배열로 바꿔주었다.
var maps = maps.map { Array($0) } // 2차원 배열로 변경을 해줬음- 2차원 배열로 바뀐 것에서 핵심좌표(시작,레버,출구)를 뽑아줬다
var START: (Int, Int)
var LABBER: (Int, Int)
var EXIT: (Int, Int)
for i in 0..<maps.count {
for j in 0..<maps[0].count {
if maps[i][j] == "S" {
START = (i, j)
}
else if maps[i][j] == "L" {
LABBER = (i, j)
}
else if maps[i][j] == "E" {
EXIT = (i, j)
}
}
}- 이제 일반적인 Dfs를하던..Bfs를 사용해서 풀어나가면 될 것 같다.
나는 원래 bfs가 좀 편했던 것 같아서 투박하지만, BFS로 풀어봤다.
import Foundation
func solution(_ maps: [String]) -> Int {
// 초기세팅
var answer = -1
var maps = maps.map { Array($0) } // 2차원 배열로 변경을 해줬음
var visited = Array(
repeating: Array(repeating: false, count: maps[0].count),
count: maps.count
)
func resetVisited() -> [[Bool]] {
return Array(
repeating: Array(repeating: false, count: maps[0].count),
count: maps.count
)
}
var START = (0, 0)
var LABBER = (0, 0)
var EXIT = (0, 0)
var move_x = [0, 0, 1, -1]
var move_y = [1, -1, 0, 0]
for i in 0..<maps.count {
for j in 0..<maps[0].count {
if maps[i][j] == "S" {
START = (i, j)
}
else if maps[i][j] == "L" {
LABBER = (i, j)
}
else if maps[i][j] == "E" {
EXIT = (i, j)
}
}
}
// 본격적 로직
func isRange(_ position: (Int, Int, Int)) -> Bool {
return position.0 >= 0 && position.1 >= 0 && position.0 < maps.count && position.1 < maps[0].count && maps[position.0][position.1] != "X"
}
var queue: [(Int, Int, Int)] = [(START.0, START.1, 0)]
var isFoundExit = false
while !queue.isEmpty {
let current = queue.removeFirst()
if !isFoundExit {
if (current.0, current.1) == LABBER {
isFoundExit = true
visited = resetVisited()
}
}
else {
if (current.0, current.1) == EXIT {
answer = current.2
}
}
for (dx, dy) in zip(move_x, move_y) {
let next_position = (
current.0 + dx,
current.1 + dy,
current.2 + 1
) // 다음 포지션
if isRange(next_position) && !visited[next_position.0][next_position.1] {
visited[next_position.0][next_position.1] = true
queue.append(next_position)
}
}
}
return answer
}채점 결과
정확성: 65.2
합계: 65.2 / 100.0예제는 곧잘 맞는다 싶더니 반반치기?정도 된 것 같다. 반례를 한 번 찾아서 돌려봐야겠다.
####반례
["SOOOL", "XXOXX", "XXOOE"]
기대값 : 10 , 나는 6 이 나왔는데, 정리하자면
L에서 다시 출발하면서 해야하는데, 나는 L까지 도착한거 4 따로, 그리고 다시 커서를 변경해서 S에서 E간거 출력! 이런식으로 했었던 것이다.
E까지 가는길에 L이 잘 위치했으면 정답이 나오지면 이것처럼 거슬러 올라가야했을 경우에는 차이가 발생했던 것!
그래서 결국엔 L에 도착했을 때 그동안 있었던 큐의 원소들을 날리고, L에 해당하는 좌표값을 남겨주면서 돌아가도록 했다
if !isFoundExit {
if (current.0, current.1) == LABBER {
queue = [current] // 큐를 다시 초기화
isFoundExit = true
visited = resetVisited()
}
}채점 결과
정확성: 100.0
합계: 100.0 / 100.0
최종제출 코드
import Foundation
func solution(_ maps: [String]) -> Int {
// 초기세팅
var answer = -1
var maps = maps.map { Array($0) } // 2차원 배열로 변경을 해줬음
var visited = Array(
repeating: Array(repeating: false, count: maps[0].count),
count: maps.count
)
func resetVisited() -> [[Bool]] {
return Array(
repeating: Array(repeating: false, count: maps[0].count),
count: maps.count
)
}
var START = (0, 0)
var LABBER = (0, 0)
var EXIT = (0, 0)
var move_x = [0, 0, 1, -1]
var move_y = [1, -1, 0, 0]
for i in 0..<maps.count {
for j in 0..<maps[0].count {
if maps[i][j] == "S" {
START = (i, j)
}
else if maps[i][j] == "L" {
LABBER = (i, j)
}
else if maps[i][j] == "E" {
EXIT = (i, j)
}
}
}
// 실제 풀이
func isRange(_ position: (Int, Int, Int)) -> Bool {
return position.0 >= 0 && position.1 >= 0 && position.0 < maps.count && position.1 < maps[0].count && maps[position.0][position.1] != "X"
}
var queue: [(Int, Int, Int)] = [(START.0, START.1, 0)]
var isFoundExit = false
while !queue.isEmpty {
let current = queue.removeFirst()
if !isFoundExit {
if (current.0, current.1) == LABBER {
queue = [current] // 큐를 다시 초기화
isFoundExit = true
visited = resetVisited()
}
}
else {
if (current.0, current.1) == EXIT {
answer = current.2
}
}
for (dx, dy) in zip(move_x, move_y) {
let next_position = (
current.0 + dx,
current.1 + dy,
current.2 + 1
) // 다음 포지션
if isRange(next_position) && !visited[next_position.0][next_position.1] {
visited[next_position.0][next_position.1] = true
queue.append(next_position)
}
}
}
return answer
}결국 맞았다. 사실 이렇게 하면 뒤늦게 도착한 L이 이상해지지 않을까? 했는데, 가까운만큼 최솟값으로 도착한애가 기준이 될 수 있구나 하는걸 다시한 번 체감했다.
타인의 코드
import Foundation
func solution(_ maps:[String]) -> Int {
let map = maps.map { $0.map { $0 } }
let col = map.count, row = map[0].count
let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]
var start = (0, 0), exit = (0, 0), lever = (0, 0)
for i in 0..<map.count {
for j in 0..<map[i].count {
switch map[i][j] {
case "S": start = (i, j)
case "E": exit = (i, j)
case "L": lever = (i, j)
default: break
}
}
}
func getFindLeverTime() -> Int {
var queue = [(start.0, start.1, 0)]
var front = 0
var visit = Array(repeating: Array(repeating: false, count: row), count: col)
visit[start.0][start.1] = true
while front < queue.count {
let (x, y, count) = queue[front]
front += 1
for i in 0...3 {
let nX = x + dx[i]
let nY = y + dy[i]
if nX == lever.0 && nY == lever.1 { return count + 1 }
if nX < 0 || nY < 0 || nX >= col || nY >= row || visit[nX][nY] { continue }
if map[nX][nY] != "X" {
queue.append((nX, nY, count + 1))
visit[nX][nY] = true
}
}
}
return -1
}
func getFindExitTime() -> Int {
var queue = [(lever.0, lever.1, 0)]
var front = 0
var visit = Array(repeating: Array(repeating: false, count: row), count: col)
visit[lever.0][lever.1] = true
while front < queue.count {
let (x, y, count) = queue[front]
front += 1
for i in 0...3 {
let nX = x + dx[i]
let nY = y + dy[i]
if nX == exit.0 && nY == exit.1 { return count + 1 }
if nX < 0 || nY < 0 || nX >= col || nY >= row || visit[nX][nY] { continue }
if map[nX][nY] != "X" {
queue.append((nX, nY, count + 1))
visit[nX][nY] = true
}
}
}
return -1
}
let leverTime = getFindLeverTime()
if leverTime == -1 { return -1 }
let exitTime = getFindExitTime()
if exitTime == -1 { return -1 }
return leverTime + exitTime
}
사실상 거의 같게 풀은 느낌.
차이가 있다면
1. 하나의 while문으로 풀것이냐, 레버부터 출구까지를 분리할 것이냐 였던 것 같다.
2. visited를 따로 분리하는 과정에서 차이가 발생했다.
3. 저는 개인적으로visited배열을 재활용하는걸 좋아해서resetVisited라는 방문배열 초기화해주는 함수를 만들어썼다. 같은 코드 안봐서 좋고 메모리 재할당도 줄일 수 있어서 이렇게 했다.
var visited = Array(
repeating: Array(repeating: false, count: maps[0].count),
count: maps.count
)
func resetVisited() -> [[Bool]] {
return Array(
repeating: Array(repeating: false, count: maps[0].count),
count: maps.count
)
}
기억보단 기록을