sky09508   1년 전

3일 째 같은 문제만 풀고 있는데요... 왜 계속 틀렸는지 모르겠네요.....

bfs로 풀었고, 바이러스는 모두 -1로 라벨링 해주었습니다. 그리고 시간은 visited에 +1씩 저장을 하는 형식으로 풀어줬습니다.

고수분들의 답변 기다리겠습니다..!!

tkvl94   1년 전

일단 반례

4 1
2 0 0 1
1 1 0 1
0 0 0 1
0 0 1 2

오답 

7

정답

-1

글쓴이분 코드의 문제로 생각 되는 부분은 바이러스를 담지 않은 map에 2가 남아있을 때 에러가 발생하는 것으로 보입니다.

추가로 조언 드리면 아래 코드 때문에 시간 초과가 발생할 가능성도 생각해볼 수 있습니다.

for (int i = x; i < n; i++) {
    int nj = (i == x) ? y : 0;
    for (int j = nj; j < n; j++) {
        if (map[i][j] == 2) {
            map[i][j] = -1; // 빈 칸과 구분하기 위하여 0이 아닌 -1로 지정.
            func(cnt + 1, i, j + 1);
            map[i][j] = 2;
        }
    }
}

이 부분은 미리 해당 바이러스를 놓을 수 있는 칸을 저장해두는 배열을 사용하면 효율성이 올라갈 것으로 보입니다.

sky09508   1년 전

감사합니다 ㅠㅠ!

문제도 해결했고 코드도 참고해보겠습니다 :)

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