[백준] (Swift) 3055번 - 탈출 (골드4) (BFS)

역시나 이문제도 골드라서 겁먹었는데, 문제를 차근차근 읽어나가면서 아이패드에 생각정리를 해보니 조건처리만 잘 해주면 쉬운 문제였다! 
근데 왤케 많이 틀렸냐고? 하하ㅏ하핳,,, 코드 수정하느라 막 print해야하는데 안해주고 print문 지워진지도 모르고 다른거 수정하고 앉아있고 생쑈를 했다. ... 아우 그냥...... 문제는 다 풀었는데 나의 잔 실수때문에 쓸데없이 버린 시간만 너무 많아서 화가 단단히 났던 문제!

 

⚫️ 문제

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

3055번: 탈출

 

⚫️ 생각의 흐름

어우,,, 문제 읽자마자 뭐이리많아?? 하면서 아이패드에 끄적이기 시작했다. ... 빈곳도 있고,, 비버 굴.. 물이차있는곳ㄱ.. 등등 우선 생각의 흐름을 정리해보자.

🔖 최소 시간을 구하라고??

아 최소시간을 구하는 거구나! 시간은 한칸 이동할때 1분이라고 치면 되는구나! 그럼 BFS를 이용해서 시작노드~도착노드까지의 최단거리를 구하면 되겠네? 고슴도치가 있는 위치를 시작노드라고 치고, 비버굴이 있는 노드를 도착노드라고 쳐서 고슴도치를 이동시켜보자. 이렇게 생각의 흐름을 가져갔다.

🔖 그렇다면 BFS를 어떻게 구현할 수 있을까?

BFS는 시작노드, 그리고 그와 인접한 노드를 모두 queue에 넣어주면서 어떤 노드까지가 최단거리일지 찾는 방식이다. 그럼, queue에 이동하려는 위치값 (x, y)과 depth를 넣어주면 되지않을까? depth에는 BFS내부에서 몇개의 간선을 지났는지 적어주자. 그럼 이게 시간이 되겠네?

🔖 BFS를 짜기전에 그럼 시간복잡도 먼저 살펴보자

BFS는 한개의 노드당 N번의 for loop를 돌게 되기 때문에 O(N)이 기본적으로 소요된다. 하지만, 여기서 또 queue 내부에 아무것도 없을 떄까지 while 반복문을 돌기 떄문에 O(N^2)이 소요된다. 

N의 범위는? 50보다 작은수다! 와,,, 최대로 돌아가도 2500번이기 때문에 BFS로 구현하는거 쌉가능이겟고만!

🔖 그럼 이제 !! BFS를 수도코드로 구현해보자

다음 시간에 물이 차는 곳은 고슴도치가 움직이지 못한다고 했다. 그럼, 물을 먼저 채워주고, 그다음 고슴도치를 움직여주면 되겠구나! 라고 생각했따. 그렇게 대충 코드를 짜본게 아래와 같다.

처음에 생각한 방식은 while문 내부에서 *(물)의 위치를 찾아주고, 물 사방을 다 물로 덮어버린 후, 고슴도치를 사방으로 이동시키는 방식이었다. 이렇게 그대로 코드를 구현했는데,,, 당연히 틀리고 말았따! 왜 틀렸냐!!!

 

❌ 틀렸습니다 (1)

틀렸을때, 머리로는 도저히 코드 수정을 못할 것 같아서 queue가 늘어나는 방식, 물은 어디에 차는지 전부 print로 찍어봤다. 문제는 바로 찾을 수 있었다.

지금 내 수도코드를 보면, while문에서 queue를 하나씩 출력할때마다 물을 채워주고 있다.
하지만 만약 인접한 노드가 많아서 queue 에 [2, 0, 1] , [2, 1, 1] 이렇게 쌓여있다고 생각해보자. (x, y, depth 순) 처음에 [2, 0, 1]이 pop 되었을 때 depth 는 1이다. 시간이 1이 지났을때의 물이 채워진 형태여야한다. 다음 queue가 pop되었을때도 마찬가지로 depth가 1이기 때문에 동일한 배열을 사용해야하는데, 여기서 나는 또! 물을 채워준 것이다.

🔖 그럼 어떻게 depth별로 물을 채워주지??

처음에 바보같이 depth가 1이면 for문으로 1번 돌려서 초기 입력받은 arr로부터 물을 1번 채워주고, depth가 2이면 또 초기 입력받은 arr로부터 for문을 depth만큼 돌려서 물을 2번 채워주고.. 이렇게 생각했다. 진짜 ㄹㅇ 1차원적인 생각 ㅋㅋㅋㅋㅋㅋ

당연히 xcode 내부에서도 결과값이 굉장히 오래 걸리도록 나오지 않는 엄청난 시간을 잡아먹었따. 그래서 생각한게....

queue를 자세히 보면, depth 순서대로 queue에 쌓이게 된다.

이렇게 큐를 print 해봤는데,, depth는 0, 0, 1,1,1,1,2,2,2,2,,,, 이렇게 하나씩 커지면서 queue에 쌓이게 된다. 그래서!! 판단한게, depth가 이전값과 달라지면? 물을 채워라!~ 이렇게 바꿨다. 

// 어차피 depth는 순서대로 증가 -> 변하면 하나 물채워진 지도로 사용
if waterfillCount != depth {
    waterfillCount = depth
    fillwater()
}

❌ 시간초과 (1)

아 왜 또 시간초과!! 왤까.... 자자.... 다시 위에 queue를 보자.

여기 드래그 해놓은데를 보면,, queue 내부에 동일한 노드가 들어있다! 왜냐면,,, 내가 방문처리를 해주지 않아서 그렇다. 초반에는 방문처리를 해주지 않아도 된다고 생각했다. 왜냐면? 왔다가 되돌아가는 route면, 어차피 depth가 한단계 커지기 때문에 결과값에는 크게 영향을 주지 않기 때문이다. 근데,, 이렇게 하게 되면 queue가 무지막지하게 커지게 되고, queue내부에서 pop하는 횟수가 더 늘어나기 때문에 더 많은 시간을 소요한다.

BFS는 queue 내부에서 잡아먹는 공간복잡도가 시간에 크게 영향을 준다는 사실을 잊었다... 아니 고새 잊었어??? 

한번 방문한 노드는 또 방문하지 않는다! 라는 조건이 없지만, 왔다가 되돌아가는 루트는 어차피 최단거리가 아니기 때문에 visited라는 배열을 하나 만들어서 방문처리를 해주고, 이런일이 없게 만들어주자.... 그래야... 시간이 조금이라도 덜들지.. 후..

그 결과,,, 통과 🥰 어우.. 시간을 너무 버렸어서 너무 기뻤다.... (컴파일 에러는 변수 명 오타나서 😅)

 

⚫️ 정답코드

아 그리고, 코드 보면 fillwater 함수 내부에서 removefirst 메서드를 사용해서 쓸데없이 시간을 잡아먹고 있는데, 이것도 개선해줬다! (코드는 그대로 주석달아서 아래 적어놨다.)

import Foundation

let rc = readLine()!.split(separator: " ").map{ Int($0)! }
var maps = [[String]]()
var start = [0, 0]
var end = [0, 0]
var water = [[Int]]()

for i in 0..<rc[0] {
    let temp = readLine()!.map{ String($0) }
    if temp.contains("D") {
        end = [i, temp.firstIndex(of: "D")!]
    }

    if temp.contains("S") {
        start = [i, temp.firstIndex(of: "S")!]
    }

    for t in temp {
        if t == "*" {
            water.append([i, temp.firstIndex(of: t)!])
        }
    }

    maps.append(temp)
}

var visited = Array(repeating: Array(repeating: false, count: rc[1]), count: rc[0])
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

func bfs() {
    var flag = false
    var queue = [[Int]]() // [x, y, depth]
    queue.append([start[0], start[1], 0])
    visited[start[0]][start[1]] = true
    var waterfillCount = -999

    while !queue.isEmpty {
        // 고슴도치 S 이동시켜주기
        let q = queue.removeFirst()
        let x = q[0]
        let y = q[1]
        let depth = q[2]

        // 어차피 depth는 순서대로 증가 -> 변하면 하나 물채워진 지도로 사용
        if waterfillCount != depth {
            waterfillCount = depth
            fillwater()
        }

        if x == end[0], y == end[1] {
            print(depth)
            flag = true
            break
        }

        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]

            if nx < 0 || ny < 0 || nx >= rc[0] || ny >= rc[1] {
                continue
            }

            // 돌이거나 물이면 pass
            if maps[nx][ny] == "X" || maps[nx][ny] == "*" {
                continue
            }

            // maps에서 비어있는곳이면, 큐에 넣어줌으로써 인접노드로 추가
            // visited 꼭해줘야 시간초과 안남 ;
            if (maps[nx][ny] == "." || maps[nx][ny] == "D"), !visited[nx][ny] {
                visited[nx][ny] = true
                queue.append([nx, ny, depth + 1])
            }
        }
    }

    if !flag {
        print("KAKTUS")
    }
}

// 물을 채워주는 함수
// 어차피 water 내부에서만 순서대로 돌리면돼
// 그리고 temp로 갱신시켜주자... O(N^2) -> O(N) 쌉가능 (이지만 두번째 시도도 시간초과가 나고 말았다)
func fillwater() {
    var temp = [[Int]]()

    for w in water {
        let waterX = w[0]
        let waterY = w[1]

        for i in 0..<4 {
            let nwx = waterX + dx[i]
            let nwy = waterY + dy[i]

            if nwx < 0 || nwy < 0 || nwx >= rc[0] || nwy >= rc[1] {
                continue
            }

            if maps[nwx][nwy] == "." {
                maps[nwx][nwy] = "*"
                temp.append([nwx, nwy])
            }
        }
    }
    water = temp
}

// ❌ 첫번째 시도 -> 시간초과
// 물 이동시키는거 -> maps 만 변화시켜주면 되는데 쓸데없이 removeFirst조지고 있었음
func timeover_fillwater() {
    let waterCnt = water.count
    var maps = maps

    for _ in 0..<waterCnt {
        let waterPlace = water.removeFirst()
        let waterX = waterPlace[0]
        let waterY = waterPlace[1]

        for i in 0..<4 {
            let nwx = waterX + dx[i]
            let nwy = waterY + dy[i]

            if nwx < 0 || nwy < 0 || nwx >= rc[0] || nwy >= rc[1] {
                continue
            }

            if maps[nwx][nwy] == "X" || maps[nwx][nwy] == "*" {
                continue
            }

            maps[nwx][nwy] = "*"
            water.append([nwx, nwy])
        }
    }
}

bfs()