<div id="readability-page-1" class="page"><div>            <h2>문제로 이동하기</h2>
<p><a href="https://www.acmicpc.net/problem/17070">https://www.acmicpc.net/problem/17070</a></p>
<h2>여담</h2>
<p>오랜만에 DP를 풀어봤습니다. 솔직히 요즘 BFS만 공부하다보니 DP에 소홀해져서 많이 걱정했는데, 스스로 이 문제를 풀게 돼서 정말 기쁘고 행복(?)했습니다! ㅋㅋㅋ 아.. 진짜 예제 입력들 전부 넣어보고 마지막 답이 정확하게 일치하는 거 보고 현실로 탄성을 질렀습니다 ㅋㅋㅋ... 잡설이지만 정말 기뻤답니다 🙂</p>
<h2>접근 방식</h2>
<p>우선 점화식을 세워봐야 합니다. 다른 어려운 문제들에 비해선 점화식을 세우기 쉬운 편인 것 같았습니다. 처음에는 너무 단순하게 생각해서 <code>D</code> 배열을 이렇게 정의했습니다.</p>
<p><code>D[i][j] = 파이프의 끝자락이 (i, j)에 위치하도록 이동시키는 방법의 수</code></p>
<p>이렇게 점화식을 세우고 문제를 접근해보니 일단 대충은 풀 수 있겠더군요. 그렇지만 정답을 찾을 수 없었습니다. 이 문제에서 핵심적인 요소는 <strong>방향</strong>입니다. 방향에 따라서 다음 이동 위치에 올 수 있는 방법이 달라지기 때문입니다. 따라서 점화식에 <strong>방향 요소</strong>도 추가해주게 되었습니다.</p>
<p><code>D[i][j][k] = 파이프가 k 방향이면서 파이프의 끝자락이 (i, j)에 위치하도록 이동시키는 방법의 수</code></p>
<p>이 때, <code>k</code>는 <code>0</code>이면 가로 방향으로, <code>1</code>이면 세로 방향으로, <code>2</code>이면 대각선 방향으로 놓여있다고 정리했습니다.</p>
<p>이번에는 현재 놓여있는 방향에 따라 직전의 방향을 결정해보겠습니다.</p>
<ul>
<li>현재 가로로 놓여 있으며, 파이프의 끝이 <code>(i, j)</code>에 위치한 경우 직전에 놓일 수 있는 경우의 수는:<ul>
<li>가로로 놓여 있었으며, 파이프의 끝이 <code>(i, j-1)</code>에 위치한 경우</li>
<li>대각선으로 놓여 있었으며, 파이프의 끝이 <code>(i, j-1)</code>에 위치한 경우</li>
</ul>
</li>
<li>현재 세로로 놓여 있으며, 파이프의 끝이 <code>(i, j)</code>에 위치한 경우 직전에 놓일 수 있는 경우의 수는:<ul>
<li>세로로 놓여 있었으며, 파이프의 끝이 <code>(i-1, j)</code>에 위치한 경우</li>
<li>대각선으로 놓여 있었으며, 파이프의 끝이 <code>(i-1, k)</code>에 위치한 경우</li>
</ul>
</li>
<li>현재 대각선으로 놓여 있으며, 파이프의 끝이 <code>(i, j)</code>에 위치한 경우 직전에 놓일 수 있는 경우의 수는:<ul>
<li>가로로 놓여 있었으며, 파이프의 끝이 <code>(i-1, j-1)</code>에 위치한 경우</li>
<li>세로로 놓여 있었으며, 파이프의 끝이 <code>(i-1, j-1)</code>에 위치한 경우</li>
<li>대각선으로 놓여 있었으며, 파이프의 끝이 <code>(i-1, j-1)</code>에 위치한 경우</li>
</ul>
</li>
</ul>
<p>또한 직전의 방향을 계산하기 전에 먼저 파악해야 하는 것은 직전의 위치가 파이프가 놓일 수 있는 위치였는지를 확인하는 것입니다. 따라서 각각의 상황에 대해 혹시나 해당 좌표의 값이 벽은 아닌지 확인해봐야 합니다. 벽이 아니라면 위에서 구한 경우를 더해주면 됩니다.</p>
<h2>점화식</h2>
<p>위에서 정리한 상황에 맞춰 점화식을 작성해보면 다음과 같습니다.</p>
<pre><code>for i := 1; i &lt;= N; i++ {
        for j := 1; j &lt;= N; j++ {
            // 가로로 i, j에 놓여있다는 것이고. 가로로 있다는 소리는
            // 1) 가로-&gt;가로 2) 대각선-&gt;가로
            if G[i][j-1] != 1 {
                D[i][j][0] += D[i][j-1][0] + D[i][j-1][2]
            }
            // 세로로 i, j에 놓여있다는 것이고, 세로로 있다는 소리는
            // 1) 세로-&gt;세로 2) 대각선-&gt;세로
            if G[i-1][j] != 1 {
                D[i][j][1] += D[i-1][j][1] + D[i-1][j][2]
            }
            // 대각선으로 i,j에 놓여있다는 것이고, 대각선으로 있다는 소리는
            // 1) 가로-&gt;대각선 2) 세로-&gt;대각선 3) 대각선-&gt;대각선
            if G[i-1][j-1] != 1 &amp;&amp; G[i][j-1] != 1 &amp;&amp; G[i-1][j] != 1 {
                D[i][j][2] += (D[i-1][j-1][0] + D[i-1][j-1][1] + D[i-1][j-1][2])
            }
        }
    }</code></pre>
<p><strong>주의!</strong><br>만약 <code>(N, N)</code>이 벽이면 어떠한 경우에도 파이프가 이동할 수 없으므로, 답은 0이 됩니다. 따라서 위의 절차를 밟을 필요도 없이 답을 출력하고 종료하면 됩니다. 이걸 몰라서... 한 번 틀렸습니다를 받았습니다 ㅠㅠ</p>
<h2>코드</h2>
<pre><code>package main

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

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

var (
    N int
    G [][]int
    D [][][]int
)

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

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

    // (N, N)이 벽인 경우, 어떠한 경우에도 도달할 수 없으므로 0을 출력하고 종료
    if G[N][N] == 1 {
        fmt.Fprintln(w, 0)
        return
    }

    // D[i][j] = 끝자락이 (i, j)에 놓이도록 이동하는 방법의 수
    // k == 0 -&gt; 가로 , k == 1 -&gt; 세로, k == 2 -&gt; 대각선
    D[1][2][0] = 1
    for i := 1; i &lt;= N; i++ {
        for j := 1; j &lt;= N; j++ {
            // 가로로 i, j에 놓여있다는 것이고. 가로로 있다는 소리는
            // 1) 가로-&gt;가로 2) 대각선-&gt;가로
            if G[i][j-1] != 1 {
                D[i][j][0] += D[i][j-1][0] + D[i][j-1][2]
            }
            // 세로로 i, j에 놓여있다는 것이고, 세로로 있다는 소리는
            // 1) 세로-&gt;세로 2) 대각선-&gt;세로
            if G[i-1][j] != 1 {
                D[i][j][1] += D[i-1][j][1] + D[i-1][j][2]
            }
            // 대각선으로 i,j에 놓여있다는 것이고, 대각선으로 있다는 소리는
            // 1) 가로-&gt;대각선 2) 세로-&gt;대각선 3) 대각선-&gt;대각선
            if G[i-1][j-1] != 1 &amp;&amp; G[i][j-1] != 1 &amp;&amp; G[i-1][j] != 1 {
                D[i][j][2] += (D[i-1][j-1][0] + D[i-1][j-1][1] + D[i-1][j-1][2])
            }
        }
    }
    fmt.Fprintln(w, sum(D[N][N]))
}

func sum(arr []int) int {
    res := 0
    for i := range arr {
        res += arr[i]
    }
    return res
}

func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}</code></pre>
<h2>마무리</h2>
<p>여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.</p>
<p>혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊</p>
                        
</div></div>

욱이의 IT 생존일지

Jaewook Oh

문제로 이동하기
https://www.acmicpc.net/problem/17070
여담
오랜만에 DP를 풀어봤습니다. 솔직히 요즘 BFS만 공부하다보니 DP에 소홀해져서 많이 걱정했는데, 스스로 이 문제를 풀게 돼서 정말 기쁘고 행복(?)했습니다! ㅋㅋㅋ 아.. 진짜 예제 입력들 전부 넣어보고 마지막 답이 정확하게 일치하는 거 보고 현실로 탄성을 질렀습니다 ㅋㅋㅋ... 잡설이지만 정말 기뻤답니다  
접근 방식
우선 점화식을 세워봐야 합니다. 다른 어려운 문제들에 비해선 점화식을 세우기 쉬운 편인 것 같았습니다. 처음에는 너무 단순하게 생각해서 D 배열을 이렇게 정의했습니다.
D[i][j] = 파이프의 끝자락이 (i, j)에 위치하도록 이동시키는 방법의 수
이렇게 점화식을 세우고 문제를 접근해보니 일단 대충은 풀 수 있겠더군요. 그렇지만 정답을 찾을 수 없었습니다. 이 문제에서 핵심적인 요소는 방향입니다. 방향에 따라서 다음 이동 위치에 올 수 있는 방법이 달라지기 때문입니다. 따라서 점화식에 방향 요소도 추가해주게 되었습니다.
D[i][j][k] = 파이프가 k 방향이면서 파이프의 끝자락이 (i, j)에 위치하도록 이동시키는 방법의 수
이 때, k는 0이면 가로 방향으로, 1이면 세로 방향으로, 2이면 대각선 방향으로 놓여있다고 정리했습니다.
이번에는 현재 놓여있는 방향에 따라 직전의 방향을 결정해보겠습니다.
현재 가로로 놓여 있으며, 파이프의 끝이 (i, j)에 위치한 경우 직전에 놓일 수 있는 경우의 수는:
가로로 놓여 있었으며, 파이프의 끝이 (i, j-1)에 위치한 경우
대각선으로 놓여 있었으며, 파이프의 끝이 (i, j-1)에 위치한 경우
현재 세로로 놓여 있으며, 파이프의 끝이 (i, j)에 위치한 경우 직전에 놓일 수 있는 경우의 수는:
세로로 놓여 있었으며, 파이프의 끝이 (i-1, j)에 위치한 경우
대각선으로 놓여 있었으며, 파이프의 끝이 (i-1, k)에 위치한 경우
현재 대각선으로 놓여 있으며, 파이프의 끝이 (i, j)에 위치한 경우 직전에 놓일 수 있는 경우의 수는:
가로로 놓여 있었으며, 파이프의 끝이 (i-1, j-1)에 위치한 경우
세로로 놓여 있었으며, 파이프의 끝이 (i-1, j-1)에 위치한 경우
대각선으로 놓여 있었으며, 파이프의 끝이 (i-1, j-1)에 위치한 경우
또한 직전의 방향을 계산하기 전에 먼저 파악해야 하는 것은 직전의 위치가 파이프가 놓일 수 있는 위치였는지를 확인하는 것입니다. 따라서 각각의 상황에 대해 혹시나 해당 좌표의 값이 벽은 아닌지 확인해봐야 합니다. 벽이 아니라면 위에서 구한 경우를 더해주면 됩니다.
점화식
위에서 정리한 상황에 맞춰 점화식을 작성해보면 다음과 같습니다.
for i := 1; i <= N; i++ {
        for j := 1; j <= N; j++ {
            // 가로로 i, j에 놓여있다는 것이고. 가로로 있다는 소리는
            // 1) 가로->가로 2) 대각선->가로
            if G[i][j-1] != 1 {
                D[i][j][0] += D[i][j-1][0] + D[i][j-1][2]
            }
            // 세로로 i, j에 놓여있다는 것이고, 세로로 있다는 소리는
            // 1) 세로->세로 2) 대각선->세로
            if G[i-1][j] != 1 {
                D[i][j][1] += D[i-1][j][1] + D[i-1][j][2]
            }
            // 대각선으로 i,j에 놓여있다는 것이고, 대각선으로 있다는 소리는
            // 1) 가로->대각선 2) 세로->대각선 3) 대각선->대각선
            if G[i-1][j-1] != 1 && G[i][j-1] != 1 && G[i-1][j] != 1 {
                D[i][j][2] += (D[i-1][j-1][0] + D[i-1][j-1][1] + D[i-1][j-1][2])
            }
        }
    }
주의!
만약 (N, N)이 벽이면 어떠한 경우에도 파이프가 이동할 수 없으므로, 답은 0이 됩니다. 따라서 위의 절차를 밟을 필요도 없이 답을 출력하고 종료하면 됩니다. 이걸 몰라서... 한 번 틀렸습니다를 받았습니다 ㅠㅠ
코드
package main
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)
var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)
var (
    N int
    G [][]int
    D [][][]int
)
func init() {
    sc.Split(bufio.ScanWords)
}
func main() {
    defer w.Flush()
    N = scanInt()
    G = make([][]int, N+1)
    D = make([][][]int, N+1)
    for i := range G {
        G[i] = make([]int, N+1)
        D[i] = make([][]int, N+1)
        for j := range D[i] {
            D[i][j] = make([]int, 3)
        }
        if i != 0 {
            for j := range G[i] {
                if j != 0 {
                    G[i][j] = scanInt()
                }
            }
        }
    }
    // (N, N)이 벽인 경우, 어떠한 경우에도 도달할 수 없으므로 0을 출력하고 종료
    if G[N][N] == 1 {
        fmt.Fprintln(w, 0)
        return
    }
    // D[i][j] = 끝자락이 (i, j)에 놓이도록 이동하는 방법의 수
    // k == 0 -> 가로 , k == 1 -> 세로, k == 2 -> 대각선
    D[1][2][0] = 1
    for i := 1; i <= N; i++ {
        for j := 1; j <= N; j++ {
            // 가로로 i, j에 놓여있다는 것이고. 가로로 있다는 소리는
            // 1) 가로->가로 2) 대각선->가로
            if G[i][j-1] != 1 {
                D[i][j][0] += D[i][j-1][0] + D[i][j-1][2]
            }
            // 세로로 i, j에 놓여있다는 것이고, 세로로 있다는 소리는
            // 1) 세로->세로 2) 대각선->세로
            if G[i-1][j] != 1 {
                D[i][j][1] += D[i-1][j][1] + D[i-1][j][2]
            }
            // 대각선으로 i,j에 놓여있다는 것이고, 대각선으로 있다는 소리는
            // 1) 가로->대각선 2) 세로->대각선 3) 대각선->대각선
            if G[i-1][j-1] != 1 && G[i][j-1] != 1 && G[i-1][j] != 1 {
                D[i][j][2] += (D[i-1][j-1][0] + D[i-1][j-1][1] + D[i-1][j-1][2])
            }
        }
    }
    fmt.Fprintln(w, sum(D[N][N]))
}
func sum(arr []int) int {
    res := 0
    for i := range arr {
        res += arr[i]
    }
    return res
}
func scanInt() int {
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    return n
}
마무리
여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.
혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글 을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다

[BOJ/17070/Golang] 백준 17070 - 파이프 옮기기 1

댓글