글 읽기 - 15683번 어디서 틀린건지 도무지 모르겠습니다...

wkd6576 3년 전 0

일단 문제에서 주어지는 테스트케이스들은 모두 제대로 나옵니다. 하지만

8 8

0 0 0 0 0 0 0 1

0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 0 1 0 0 0

0 1 0 0 0 0 0 0

이 테스트 케이스에서 무한루프에 빠집니다. 아무리 생각해봐도 코드의 어떤 부분이 잘못되어서 무한루프에 빠지는지 도무지 이해가 가지 않습니다..

function solve(N, M, graph, CCTV) {
    let visited = Array.from(new Array(N), () => new Array(M).fill(0))
    const Directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    let result = 987654321

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (graph[i][j] === 5) {
                visited[i][j] = 1
                for (let k = 0; k < 4; k++) {
                    change(i, j, k)
                }
            }
        }
    }
    function change(x, y, k) {
        let nextX = x + Directions[k][0]
        let nextY = y + Directions[k][1]

        if (0 <= nextX && nextX < N && 0 <= nextY && nextY < M && graph[nextX][nextY] !== 6) {
            if (1 <= graph[nextX][nextY] && graph[nextX][nextY] <= 5) {
                change(nextX, nextY, k)
            }
            else {
                graph[nextX][nextY] += 7
                change(nextX, nextY, k)
            }
        }
    }


    function unChange(x, y, k) {
        let nextX = x + Directions[k][0]
        let nextY = y + Directions[k][1]

        if (0 <= nextX && nextX < N && 0 <= nextY && nextY < M && graph[nextX][nextY] !== 6) {
            if (1 <= graph[nextX][nextY] && graph[nextX][nextY] <= 5) {
                unChange(nextX, nextY, k)
            }
            else {
                graph[nextX][nextY] -= 7
                unChange(nextX, nextY, k)
            }
        }
    }

    function dfs(cnt) {

        if (cnt === CCTV) {
            let ans = 0
            for (let i = 0; i < N; i++) {
                for (let j = 0; j < M; j++) {
                    if (!graph[i][j]) {
                        ans++
                    }
                }
            }
            console.log(ans)
            if (ans < result) {
                result = ans
            }
            return
        }



        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (1 <= graph[i][j] && graph[i][j] <= 5 && !visited[i][j]) {
                    if (graph[i][j] === 1) {
                        for (let k = 0; k < 4; k++) {
                            visited[i][j] = 1
                            change(i, j, k)
                            dfs(cnt + 1)
                            visited[i][j] = 0
                            unChange(i, j, k)
                        }
                    }
                    else if (graph[i][j] === 2) {
                        for (let k = 0; k < 2; k++) {
                            visited[i][j] = 1
                            change(i, j, k)
                            change(i, j, k + 2)
                            dfs(cnt + 1)
                            visited[i][j] = 0
                            unChange(i, j, k)
                            unChange(i, j, k + 2)
                        }
                    }
                    else if (graph[i][j] === 3) {
                        for (let k = 0; k < 4; k++) {
                            visited[i][j] = 1
                            change(i, j, k)
                            change(i, j, (k + 1) % 4)
                            dfs(cnt + 1)
                            visited[i][j] = 0
                            unChange(i, j, k)
                            unChange(i, j, (k + 1) % 4)
                        }
                    }
                    else if (graph[i][j] === 4) {
                        for (let k = 0; k < 4; k++) {
                            visited[i][j] = 1
                            for (let n = 0; n < 4; n++) {
                                if (k !== n) {
                                    change(i, j, n)
                                }
                            }
                            dfs(cnt + 1)
                            visited[i][j] = 0
                            for (let n = 0; n < 4; n++) {
                                if (k !== n) {
                                    unChange(i, j, n)
                                }
                            }

                        }
                    }
                }
            }
        }

    }
    dfs(0)
    console.log(result)
}



const fs = require('fs');
const stdin = (process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `8 8 
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0`
).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const [N, M] = input().split(' ').map(Number)
let cntCCTV = 0
let graph = []
for (let i = 0; i < N; i++) {
    graph.push(input().split(' ').map(Element => {
        if ('1' <= Element && Element <= '4') {
            cntCCTV++
        }
        return parseInt(Element)
    }))
}
solve(N, M, graph, cntCCTV)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

15683번 어디서 틀린건지 도무지 모르겠습니다...

wkd6576 3년 전 0

일단 문제에서 주어지는 테스트케이스들은 모두 제대로 나옵니다. 하지만

8 8

0 0 0 0 0 0 0 1

0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 0 1 0 0 0

0 1 0 0 0 0 0 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말