[BOJ/16946/Golang] 백준 16946 - 벽 부수고 이동하기 4

문제로 이동하기

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

여담

아... 처음엔 시간초과로, 이후엔 갈피를 잡지 못하다가, 결국 힌트를 보고 나서야 아 맞네!! 하고 바로 풀어냈습니다 ㅋㅋㅋ 엄청 단순하게 생각했는데.. 어림도 없지! ㅜㅜ

접근 방식

단순하게 생각하면, 매번 벽을 만날 때마다, 주변에 몇 개의 공간이 있는지 일일이 세면서 진행하는 방법도 생각해볼 수 있습니다. 하지만, 이렇게 하는 경우, O((N^3)(M^3)) 이라는 시간 복잡도를 얻게 됩니다. NM이 10만이라는 점을 고려해볼 때, 이 방법으로는 불가능하다는 결론에 이르게 됩니다. 그리고 저는 이를 미리 생각치 않아 시간 초과로 고생을 좀 했습니다..

반면, 연결된 빈 방의 개수를 그룹별로 미리 한 번에 구해두고 사용한다면 어떨까요? 이렇게 하면, 한 번의 탐색을 통해서 벽이 아닌 공간의 개수를 각각 세어둘 수 있습니다.

저는 이 탐색을 위해 DFS를 사용했습니다.

공간 구해두기

// main 내부
id := 0
for i := 1; i <= N; i++ {
    for j := 1; j <= M; j++ {
        if G[i][j] == 0 && D[i][j] == 0 {
            id++
            group[id] = 0
            dfs(i, j, id)
        }
    }
}

// main 외부
func dfs(x, y, id int) {
    D[x][y] = id
    group[id]++
    for k := range dx {
        nx, ny := x+dx[k], y+dy[k]
        if 1 <= nx && nx <= N && 1 <= ny && ny <= M {
            if G[nx][ny] == 0 && D[nx][ny] == 0 {
                dfs(nx, ny, id)
            }
        }
    }
}

코드를 보고 이해를 해보시는게 더 빠를 수도 있을 것 같습니다. DFS 탐색을 하면서 특정 공간이 어느 그룹에 속하는지 지정해주고, 그 그룹에는 몇 개의 빈 공간이 존재하는지 map 자료구조에 저장해둡니다.

벽을 탐색하며 벽 주변에 공간 그룹 구하기

for i := 1; i <= N; i++ {
        for j := 1; j <= M; j++ {
            if G[i][j] == 1 {
                answer[i][j] = 1
                checkedGroup := make([]int, 0, 4)
                for k := range dx {
                    nx, ny := i+dx[k], j+dy[k]
                    if 1 <= nx && nx <= N && 1 <= ny && ny <= M {
                        groupID := D[nx][ny]
                        if isCheckedGroup(groupID, checkedGroup) {
                            continue
                        }
                        checkedGroup = append(checkedGroup, groupID)
                        answer[i][j] += group[groupID]
                    }
                }
            }
        }
    }

코드가 쓸데 없이 길기는 합니다만, 사실 로직은 간단합니다.

1. 벽 사방으로 공간을 탐색합니다.
2. 공간이 존재하면, 해당 공간이 어느 그룹에 속하는지 확인합니다.
3. 공간 그룹은 중복되어선 안 됩니다. 따라서 그룹에 대한 중복 제거를 해주어야 합니다. 여기서는 isCheckedGroup() 메서드를 구현해서 사용했습니다.
4. 마지막으로 중복되지 않은 그룹들을 순회하며, 해당 그룹의 공간 개수를 모두 더해줍니다.

이렇게 하면 벽 주변에 있는 빈 공간의 개수를 모두 셀 수 있습니다. 생각보다 그렇게 어렵지 않은 문제이니, 코드를 보시면서 이해해보시면 좋을 것 같습니다.

코드

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

var (
    N, M   int
    answer [][]int
    D      [][]int
    G      [][]int
    group  map[int]int
    dx     = [4]int{1, -1, 0, 0}
    dy     = [4]int{0, 0, 1, -1}
)

type pair struct {
    x, y int
}

func init() {
    sc.Split(bufio.ScanWords)
}

func main() {
    defer w.Flush()
    N, M = scanInt(), scanInt()
    answer = make([][]int, N+1)
    G = make([][]int, N+1)
    D = make([][]int, N+1)
    group = make(map[int]int)
    for i := range G {
        if i != 0 {
            G[i] = scanGraph()
        }
        D[i] = make([]int, M+1)
        answer[i] = make([]int, M+1)
    }

    id := 0
    for i := 1; i <= N; i++ {
        for j := 1; j <= M; j++ {
            if G[i][j] == 0 && D[i][j] == 0 {
                id++
                group[id] = 0
                dfs(i, j, id)
            }
        }
    }

    for i := 1; i <= N; i++ {
        for j := 1; j <= M; j++ {
            if G[i][j] == 1 {
                answer[i][j] = 1
                checkedGroup := make([]int, 0, 4)
                for k := range dx {
                    nx, ny := i+dx[k], j+dy[k]
                    if 1 <= nx && nx <= N && 1 <= ny && ny <= M {
                        groupID := D[nx][ny]
                        if isCheckedGroup(groupID, checkedGroup) {
                            continue
                        }
                        checkedGroup = append(checkedGroup, groupID)
                        answer[i][j] += group[groupID]
                    }
                }
            }
        }
    }

    for i := 1; i <= N; i++ {
        for j := 1; j <= M; j++ {
            fmt.Fprintf(w, "%d", answer[i][j]%10)
        }
        fmt.Fprintln(w)
    }
}

func isCheckedGroup(target int, group []int) bool {
    for i := range group {
        if target == group[i] {
            return true
        }
    }
    return false
}

func dfs(x, y, id int) {
    D[x][y] = id
    group[id]++
    for k := range dx {
        nx, ny := x+dx[k], y+dy[k]
        if 1 <= nx && nx <= N && 1 <= ny && ny <= M {
            if G[nx][ny] == 0 && D[nx][ny] == 0 {
                dfs(nx, ny, id)
            }
        }
    }
}

func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}

func scanGraph() []int {
    sc.Scan()
    s := strings.Split("0"+sc.Text(), "")
    res := make([]int, len(s))
    for i := range s {
        res[i], _ = strconv.Atoi(s[i])
    }
    return res
}

마무리

여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.

혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊