[백준] 탈출 (3055번) Swift

문제 내용

R x C 의 배열이 주어진다.

"D" 는 도착 위치 (비버의 굴), "S" 는 시작 위치 (고슴도치 위치),

"X" 는 이동 불가 (돌), "*" 는 물 위치, "." 은 빈 공간 이다.

 

"S" 는 상하좌우 한칸씩 움직일 수 있고, 움직이고 나면 물이 상하좌우 한칸씩 움직인다.

"S" 는 "." 만 이동할 수 있다.

만약 "S" 에서 "D" 까지 이동 가능하면 최소 시간을 출력하고, 이동 불가능하면 "KAKTUS" 를 출력해라.

---

전체 코드

// 1. R, C 불러옴
let size = readLine()!.split { $0 == " " }.map { Int(String($0))! }
// 2. 위치를 저장할 location 배열
var location: [[Int]] = Array(repeating: Array(repeating: 0, count: size[1]), count: size[0])
// 3. 방문했음을 저장할 배열
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: size[1]), count: size[0])
// 4. 물도 상하좌우로 방문하기 때문에 물 위치를 저장할 배열
var water: [(x: Int, y: Int)] = []
// 5. 물 업데이트 시작 위치를 저장할 waterIndex
var waterIndex = 0
// 6. 비버의 굴 위치
var destination: (x: Int, y: Int) = (0, 0)
// 7. queue
var queue: [(x: Int, y: Int)] = []
var queueIndex = 0
// 8. 얼만큼 이동했는지 저장할 값
var queueLevel = 0
// 9. 결과 값
var result = -1

// 10. location 값 불러오기
for i in 0..<size[0] {
    let row = readLine()!.map { String($0) }
    
    for j in 0..<size[1] {
        switch row[j] {
        // 11. "D" (비버의 굴) 일 때
        case "D":
            // destination 갱신하고 location 에 2로 저장함
            destination = (i, j)
            location[i][j] = 2
        // 12. "X" (벽) 일 때
        case "X":
            // 1로 저장
            location[i][j] = 1
        // 13. "S" (시작 지점) 일 때
        case "S":
            // queue 에 저장함 (queue 의 최초의 시작은 S 의 위치이므로)
            queue.append((i, j))
        // 14. "*" (물) 일 떄
        case "*":
            // water 배열에 위치를 저장하고 location 에 -1 로 저장
            water.append((i, j))
            location[i][j] = -1
        default:
            continue
        }
    }
}

// 15. BFS 반복문
outer: while queueIndex < queue.count {
    // 16. 현재 저장된 queue 의 끝 위치를 저장하기 위한 queueCount
    let queueCount = queue.count
    
    // 17. queueIndex 에서 시작해서 queueCount 전까지 반복
    // 이유는 visit 함수에서 queue 에 append 를 하므로 queue.count 가 값이 변할 수 있음
    for i in queueIndex..<queueCount {
        let now = queue[i]
        
        // 18. 만약 현재 값이 도착점이면 종료
        if now == destination {
            result = queueLevel
            break outer
        }
        
        // 19. 만약 현재 위치가 0 (0은 빈 공간 또는 S 의 위치) 이고 방문하지 않았다면 방문
        if location[now.x][now.y] == 0 && !visited[now.x][now.y] {
            visit(now.x, now.y)
        }
    }
    
    // 20. water 에 대해서도 업데이트 (상하좌우 이동) 해줌
    updateWater()
    
    // 21. queueIndex 갱신
    queueIndex = queueCount
    // 22. queueLevel 을 증가시킨다 (한칸씩 진행했으므로)
    queueLevel += 1
}

func visit(_ x: Int, _ y: Int) {
    // 23. 먼저 방문했다고 체크함
    visited[x][y] = true
    // 24. x,y 에 대한 이동
    let moves: [(x: Int, y: Int)] = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
    
    for move in moves {
        // 25. 만약 이동할 위치가 이동이 가능하고
        // 이동할 위치가 0 이거나 2 이고
        // 그리고 방문하지 않았다면 queue 에 넣음
        if move.x >= 0 && move.x < size[0] && move.y >= 0 && move.y < size[1] && (location[move.x][move.y] == 0 || location[move.x][move.y] == 2) && !visited[move.x][move.y] {
            queue.append(move)
        }
    }
}

func updateWater() {
    // 26. water 의 현재 끝 위치를 저장할 waterCount
    let waterCount = water.count
    
    for i in waterIndex..<waterCount {
        // 27. x, y 에 대한 이동
        let moves: [(x: Int, y: Int)] = [(water[i].x + 1, water[i].y), (water[i].x - 1, water[i].y),
                                         (water[i].x, water[i].y + 1), (water[i].x, water[i].y - 1)
        ]
        
        for move in moves {
            // 28. 만약 이동이 가능한 위치이고
            // 그 위치가 0 (빈 위치) 이고
            // water 배열에 값이 저장이 되어 있지 않다면
            if move.x >= 0 && move.x < size[0] && move.y >= 0 && move.y < size[1] &&
                location[move.x][move.y] == 0 && !water.contains(where: { $0 == move}) {
                // 그 위치를 -1 로 만들고, water 에 넣음
                location[move.x][move.y] = -1
                water.append(move)
            }
        }
    }
    
    // 29. waterIndex 갱신
    waterIndex = waterCount
}

// 30. 만약 결과 값이 -1 (바뀌지 않음) 이라면 "KAKTUS" 를 출력하고 아니면 result 출력
print(result == -1 ? "KAKTUS" : result)

---

결론

방문한 것에 대해 체크를 안했는데 메모리 초과가 났다.

queue 의 크기가 너무 커져서 메모리가 초과가 난다 생각해서 queueIndex 를 적절히 이용해서 queue 사이즈를 줄여줬는데

그래도 메모리 초과가 나서 방문 체크를 하니까 잘 풀렸다.

 

코드를 읽기 쉽게 짜려고 하는데 막상 문제 풀기에 급급해서 깔끔하게 못푸는 것 같다.

 

출처 : 백준 탈출

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

3055번: 탈출