[백준] 5427 불 - Swift (Feat: 12%에서 틀렸던 문제)

일주일 동안 못 풀었던 문제를 일주일 만에 드디어!!! 풀었기 때문에 기록해 보려고 합니다! 🧡

 

문제는

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

5427번: 불

백준 5427번의 불 문제이며, 티어는 골드 4입니다.

 

저는 일단 testCase를 입력 받고, testCase만큼 for문을 돌려 주는 코드로 시작하였습니다.

여러 testCase가 반복되기 때문에 그래프의 초기화를 잘해 주어야 하는데요. 저는 매번 초기화해 주는 작업에서 실수를 할까 봐, testCase가 시작 될 때마다 그래프를 생성해 주는 흐름으로 코드를 작성하였습니다.

 

입력 후 상근이 큐, 불 큐에 x, y 값을 담는 코드

let testCase = Int(readLine()!)!

for _ in 0..<testCase {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let width = input[0]
    let height = input[1]
    var graph = [[String]]()
    
    var queue = [(Int, Int)]()
    var fireQueue = [(Int, Int)]()
    
    let dx = [-1, 1, 0, 0]
    let dy = [0, 0, -1, 1]
    
    // 상근이와 불의 위치 큐에 담기
    for i in 0..<height {
        let input = readLine()!.map{String($0)}
        graph.append(input)
        
        for j in 0..<width {
            if input[j] == "@" {
                queue.append((i, j))
            } else if input[j] == "*" {
                fireQueue.append((i, j))
            }
        }
    }

그리고 입력을 받음과 동시에 상근이와 불에 대한 x와 y 값을 각각의 큐에 담아 주었습니다.

 

저는 상근이가 이동할 수 없을 때가지의 조건으로 큰 while문을 하나 선언하고,

그 안에

불을 먼저 번지게 해 주고,

그 다음에 상근이를 이동시켜 주는 코드를 작성하였습니다.

 

상근이가 이동할 수 없을 때까지의 조건으로 큰 while문을 선언하고, 그안에 불과 상근이가 이동하는 코드

    var fireIndex = 0
    var queueIndex = 0
    var count = 0
    var flag = false
    
    // 상근이가 이동할 수 없을 때까지 도는 큰 while문
    while queue.count > queueIndex {
        count += 1
        
        // 불 퍼트리기
        for _ in 0..<fireQueue.count-fireIndex {
            let (y, x) = fireQueue[fireIndex]
            fireIndex += 1
            
            for i in 0..<4 {
                let nx = dx[i] + x
                let ny = dy[i] + y
                
                if 0..<width ~= nx && 0..<height ~= ny && graph[ny][nx] != "#" && graph[ny][nx] != "*" {
                    graph[ny][nx] = "*"
                    fireQueue.append((ny, nx))
                }
            }
        }
        
        // 상근이 이동하기
        for _ in 0..<queue.count-queueIndex {
            let (y, x) = queue[queueIndex]
            queueIndex += 1
            
            for i in 0..<4 {
                let nx = dx[i] + x
                let ny = dy[i] + y
                
                if 0..<width ~= nx && 0..<height ~= ny {
                    if graph[ny][nx] == "." {
                        graph[ny][nx] = "@"
                        queue.append((ny, nx))
                    }
                // 상근이가 탈출했을 때
                } else {
                    print(count)
                    flag = true
                    // nx, ny를 도는 for문 break
                    break
                }
            }
            if flag {
                // 상근이 이동하는 for문 break
                break
            }
        }
        // 전체 큰 for문 break
        if flag {
            break
        }
    }
    // 더이상 이동할 수 없을 때
    if !flag {
        print("IMPOSSIBLE")
    }
}

스위프트에 큐가 없어서 큐라는 이름의 배열을 하나 선언해, 그 index에 접근하는 코드입니다.

그럼 이제 하나씩 살펴보겠습니다.

 

불 이동시키는 반복문

	for _ in 0..<fireQueue.count-fireIndex {
            let (y, x) = fireQueue[fireIndex]
            fireIndex += 1
            
            for i in 0..<4 {
                let nx = dx[i] + x
                let ny = dy[i] + y
                
                if 0..<width ~= nx && 0..<height ~= ny && graph[ny][nx] != "#" && graph[ny][nx] != "*" {
                    graph[ny][nx] = "*"
                    fireQueue.append((ny, nx))
                }
            }
        }

 

불이 한 개만 번지는 것이 아니라, 두 개의 불이 동시에 번질 수 있기 때문에, 불을 담은 큐의 개수-불의인덱스 만큼의 for문을 돌려 주었습니다. 참고로 조건문은 그래프의 범위를 벗어나지 않고, 벽이 아니어야 하고, 같은 불이 아닐 때 불이 번지게 해 주었습니다.

 

상근이 이동 반복문

       for _ in 0..<queue.count-queueIndex {
            let (y, x) = queue[queueIndex]
            queueIndex += 1
            
            for i in 0..<4 {
                let nx = dx[i] + x
                let ny = dy[i] + y
                
                if 0..<width ~= nx && 0..<height ~= ny {
                    if graph[ny][nx] == "." {
                        graph[ny][nx] = "@"
                        queue.append((ny, nx))
                    }
                // 상근이가 탈출했을 때
                } else {
                    print(count)
                    flag = true
                    // nx, ny를 도는 for문 break
                    break
                }
            }
            if flag {
                // 상근이 이동하는 for문 break
                break
            }
        }

여기서부터 코드가 살짝 복잡해지는데...

그래프 범위를 벗어나지 않았고, 빈 공간이 있을 경우 상근이를 이동시킵니다.

 

만약 그래프 범위를 벗어났을 경우 count 값을 print 하고, ture 값을 주며, for문을 빠져 나옵니다.

 

전체 코드

let testCase = Int(readLine()!)!

for _ in 0..<testCase {
    let input = readLine()!.split(separator: " ").map{Int(String($0))!}
    let width = input[0]
    let height = input[1]
    var graph = [[String]]()
    
    var queue = [(Int, Int)]()
    var fireQueue = [(Int, Int)]()
    
    let dx = [-1, 1, 0, 0]
    let dy = [0, 0, -1, 1]
    
    // 상근이와 불의 위치 큐에 담기
    for i in 0..<height {
        let input = readLine()!.map{String($0)}
        graph.append(input)
        
        for j in 0..<width {
            if input[j] == "@" {
                queue.append((i, j))
            } else if input[j] == "*" {
                fireQueue.append((i, j))
            }
        }
    }
    
    var fireIndex = 0
    var queueIndex = 0
    var count = 0
    var flag = false
    
    while queue.count > queueIndex {
        count += 1
        
        // 불 퍼트리기
        for _ in 0..<fireQueue.count-fireIndex {
            let (y, x) = fireQueue[fireIndex]
            fireIndex += 1
            
            for i in 0..<4 {
                let nx = dx[i] + x
                let ny = dy[i] + y
                
                if 0..<width ~= nx && 0..<height ~= ny && graph[ny][nx] != "#" && graph[ny][nx] != "*" {
                    graph[ny][nx] = "*"
                    fireQueue.append((ny, nx))
                }
            }
        }
        
        // 상근이 이동하기
        for _ in 0..<queue.count-queueIndex {
            let (y, x) = queue[queueIndex]
            queueIndex += 1
            
            for i in 0..<4 {
                let nx = dx[i] + x
                let ny = dy[i] + y
                
                if 0..<width ~= nx && 0..<height ~= ny {
                    if graph[ny][nx] == "." {
                        graph[ny][nx] = "@"
                        queue.append((ny, nx))
                    }
                // 상근이가 탈출했을 때
                } else {
                    print(count)
                    flag = true
                    // nx, ny를 도는 for문 break
                    break
                }
            }
            if flag {
                // 상근이 이동하는 for문 break
                break
            }
        }
        // 전체 큰 for문 break - 여기 적는 거 깜빡...
        if flag {
            break
        }
    }
    // 더이상 이동할 수 없을 때
    if !flag {
        print("IMPOSSIBLE")
    }
}

전체 코드를 보면 이러한데, 저는 다음 x, y를 탐색하는 for문과 상근이를 이동시키는 for문, 상근이가 더이상 이동할 수 없는 while문까지 해서, 값을 찾았을 경우 세 개의 반복문을 빠져나와야 하는 코드를 작성해야 했습니다. 하지만 마지막에 전체 큰 for문 break 주석이 달린 break를 깜박해 12%에서 계속 틀렸다는 답이 나왔습니다. ㅠㅠ

 

그에 따른 반례로는

1

 3 3

 .@#

 .**

 ***

가 있습니다.

 

이 반례를 제 코드에 대입해 보면, 상근이가 바로 탈출할 수도 있지만, 불이 아직 번지지 않아서 0, 0으로 이동할 수도 있습니다.

그렇게 되면 queue에 0.0이 담기게 되고, 상근이가 빠져나간 다음 1이라는 값이 출력이 되지만, 가장 큰 queue.count > queueIndex문을 break 해 주지 않아서 (0, 0)으로 또 반복문을 돌게 됩니다 ㅠㅠ...

 

디버깅하기 굉장히 까다로운 코드였던 것 같습니다...!

불을 이동시키는 함수, 상근이를 이동시키는 함수를 만들어서 함수화된 코드를 작성했다면 좀 덜 까다롭지 않았을까 싶네요...! (이래서 함수화를 하나 봅니다!!)

 

아무튼... 저의 삽질이 다른 분들에게 도움이 되었기를 바라며... 조만간 함수화된 코드로도 다시 이 문제를 풀어 봐야겠습니다. :)