<div id="readability-page-1" class="page"><div>            <h2>문제로 이동하기</h2>
<p><a href="https://www.acmicpc.net/problem/16946">https://www.acmicpc.net/problem/16946</a></p>
<h2>여담</h2>
<p>아... 처음엔 시간초과로, 이후엔 갈피를 잡지 못하다가, 결국 힌트를 보고 나서야 아 맞네!! 하고 바로 풀어냈습니다 ㅋㅋㅋ 엄청 단순하게 생각했는데.. 어림도 없지! ㅜㅜ</p>
<h2>접근 방식</h2>
<p>단순하게 생각하면, 매번 벽을 만날 때마다, 주변에 몇 개의 공간이 있는지 일일이 세면서 진행하는 방법도 생각해볼 수 있습니다. 하지만, 이렇게 하는 경우, <code>O((N^3)(M^3))</code> 이라는 시간 복잡도를 얻게 됩니다. <code>NM</code>이 10만이라는 점을 고려해볼 때, 이 방법으로는 불가능하다는 결론에 이르게 됩니다. 그리고 저는 이를 미리 생각치 않아 시간 초과로 고생을 좀 했습니다..</p>
<p>반면, 연결된 빈 방의 개수를 그룹별로 미리 한 번에 구해두고 사용한다면 어떨까요? 이렇게 하면, 한 번의 탐색을 통해서 벽이 아닌 공간의 개수를 각각 세어둘 수 있습니다.</p>
<p>저는 이 탐색을 위해 DFS를 사용했습니다.</p>
<h2>공간 구해두기</h2>
<pre><code>// main 내부
id := 0
for i := 1; i &lt;= N; i++ {
    for j := 1; j &lt;= M; j++ {
        if G[i][j] == 0 &amp;&amp; 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 &lt;= nx &amp;&amp; nx &lt;= N &amp;&amp; 1 &lt;= ny &amp;&amp; ny &lt;= M {
            if G[nx][ny] == 0 &amp;&amp; D[nx][ny] == 0 {
                dfs(nx, ny, id)
            }
        }
    }
}</code></pre>
<p>코드를 보고 이해를 해보시는게 더 빠를 수도 있을 것 같습니다. DFS 탐색을 하면서 특정 공간이 어느 그룹에 속하는지 지정해주고, 그 그룹에는 몇 개의 빈 공간이 존재하는지 map 자료구조에 저장해둡니다.</p>
<h2>벽을 탐색하며 벽 주변에 공간 그룹 구하기</h2>
<pre><code>for i := 1; i &lt;= N; i++ {
        for j := 1; j &lt;= 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 &lt;= nx &amp;&amp; nx &lt;= N &amp;&amp; 1 &lt;= ny &amp;&amp; ny &lt;= M {
                        groupID := D[nx][ny]
                        if isCheckedGroup(groupID, checkedGroup) {
                            continue
                        }
                        checkedGroup = append(checkedGroup, groupID)
                        answer[i][j] += group[groupID]
                    }
                }
            }
        }
    }</code></pre>
<p>코드가 쓸데 없이 길기는 합니다만, 사실 로직은 간단합니다. </p>
<ol>
<li>벽 사방으로 공간을 탐색합니다.</li>
<li>공간이 존재하면, 해당 공간이 어느 그룹에 속하는지 확인합니다.</li>
<li>공간 그룹은 중복되어선 안 됩니다. 따라서 그룹에 대한 중복 제거를 해주어야 합니다. 여기서는 <code>isCheckedGroup()</code> 메서드를 구현해서 사용했습니다.</li>
<li>마지막으로 중복되지 않은 그룹들을 순회하며, 해당 그룹의 공간 개수를 모두 더해줍니다. </li>
</ol>
<p>이렇게 하면 벽 주변에 있는 빈 공간의 개수를 모두 셀 수 있습니다. 생각보다 그렇게 어렵지 않은 문제이니, 코드를 보시면서 이해해보시면 좋을 것 같습니다.</p>
<h2>코드</h2>
<pre><code>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 &lt;= N; i++ {
        for j := 1; j &lt;= M; j++ {
            if G[i][j] == 0 &amp;&amp; D[i][j] == 0 {
                id++
                group[id] = 0
                dfs(i, j, id)
            }
        }
    }

    for i := 1; i &lt;= N; i++ {
        for j := 1; j &lt;= 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 &lt;= nx &amp;&amp; nx &lt;= N &amp;&amp; 1 &lt;= ny &amp;&amp; ny &lt;= M {
                        groupID := D[nx][ny]
                        if isCheckedGroup(groupID, checkedGroup) {
                            continue
                        }
                        checkedGroup = append(checkedGroup, groupID)
                        answer[i][j] += group[groupID]
                    }
                }
            }
        }
    }

    for i := 1; i &lt;= N; i++ {
        for j := 1; j &lt;= 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 &lt;= nx &amp;&amp; nx &lt;= N &amp;&amp; 1 &lt;= ny &amp;&amp; ny &lt;= M {
            if G[nx][ny] == 0 &amp;&amp; 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
}</code></pre>
<h2>마무리</h2>
<p>여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.</p>
<p>혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊</p>
                        
</div></div>

욱이의 IT 생존일지

Jaewook Oh

문제로 이동하기
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]
                    }
                }
            }
        }
    }
코드가 쓸데 없이 길기는 합니다만, 사실 로직은 간단합니다. 
벽 사방으로 공간을 탐색합니다.
공간이 존재하면, 해당 공간이 어느 그룹에 속하는지 확인합니다.
공간 그룹은 중복되어선 안 됩니다. 따라서 그룹에 대한 중복 제거를 해주어야 합니다. 여기서는 isCheckedGroup() 메서드를 구현해서 사용했습니다.
마지막으로 중복되지 않은 그룹들을 순회하며, 해당 그룹의 공간 개수를 모두 더해줍니다. 
이렇게 하면 벽 주변에 있는 빈 공간의 개수를 모두 셀 수 있습니다. 생각보다 그렇게 어렵지 않은 문제이니, 코드를 보시면서 이해해보시면 좋을 것 같습니다.
코드
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
}
마무리
여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.
혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글 을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다

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

댓글