Resolved2022-07-25T11:11:15.642Z

lll

16 asked

for (int i = here; i <= h; i++) {

    for (int j = 1; j <= n; j++) {

        if (visited[i][j] || visited[i][j - 1] || visited[i][j + 1]) continue;

        visited[i][j] = 1;

        go(i, cnt + 1);

        visited[i][j] = 0;

    }

}

#include <bits/stdc++.h>

using namespace std;

int N, M, H;

int arr[34][12];

int res = 5;

bool simul() {

    for (int i = 1; i <= N; i++) {

        int depth = 0;

        int idx = i;

        while (depth <= H) {

            int point = arr[depth][idx];

            if (point == 1)

                idx++;

            else if (point == 2)

                idx--;

            depth++;

        }

        if (idx != i) return false;

    }

    return true;

}

void dfs(int hn, int level) {

    if (level >= res || level > 3) return;

    cout << hn << endl;

    int h = hn / 100;

    int n = hn % 100;

    if (hn == H * 100 + N) {

        if (simul()) {

            res = min(level, res);

        }

        return;

    }

    int nh = n < N ? h : h + 1;

    int nn = n < N ? n + 1 : 1;

    dfs(nh * 100 + nn, level);

    if (n < N && !arr[h][n] && !arr[h][n + 1]) {

        arr[h][n] = 1, arr[h][n + 1] = 2;

        dfs(nh * 100 + nn, level + 1);

        arr[h][n] = 0, arr[h][n + 1] = 0;

    }

}

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    cin >> N >> M >> H;

    for (int i = 0; i < M; i++) {

        int x, y;

        cin >> x >> y;

        arr[x][y] = 1;

        arr[x][y + 1] = 2;

    }

    dfs(101, 0);

    if (res == 5)

        cout << -1;

    else

        cout << res;

    return 0;

}

1

lll님 안녕하세요. ㅎㅎ 

좋은 풀이입니다.  나중에 색종이붙이기 문제를 푸시는데 그 코드와 유사합니다. y와 x를 * 1000을 통해서 인덱스를 잡고 들어가며 순차적으로 x, 다 전진 이후 y 이렇게 드가는 코드. 훌륭합니다.

 

일단 lll님의 코드 중 로직상 틀린점은 없는 것같습니다.   

simul함수 : ok

dfs : ok

그렇다면 혹시나. 중복적인 함수호출은 많이 하는 것이 아닌가? 그 또한 아닙니다.  

혹시나 운좋게 예제코드를 맞은 것은 아닌가? 사다리 잘 지었는지 확인해봤는데 그 또한 아닙니다.

 

but, 그러면 이 코드에서 어떻게 하면 시간초과를 해결할 수 있을까? 

함수호출을 줄입니다. : http://boj.kr/c59a3833193041fa90a52167c5900eff

 - 이렇게 해결하시면 됩니다. 

 

[문의 답변]

Hㅁㅁㅁㅁㅁ 를 탐색하고 난 이후에 for (int j = 1; j <= n; j++)부분으로 인해서 첫번째 공간에 사다리를 또 놓게되는 중복이 발생하지는 않는지 궁금합니다.

>> 네 중복발생합니다. 

>> but, 이 문제의 경우 n의 크기가 작아서 그닥 영향은 끼치지 않아요. 또한 continue가 있어서 함수호출부분에 있어서 중복적인 함수호출이 발생하지 않습니다. 

 

감사합니다. 

강사 큰돌 올림.

 

 

 

0

우와 ... 이거때문에 진짜 고생하고있었는데 답변해주셔서 감사합ㄴ니다 ㅜㅜㅜ

level < 3 조건만 추가 하니까 아슬아슬 통과하네요 ..! 3넘어가면 바로 return 해서 차이가 없을 줄 알았는데 ... 덕분에 하나더 배워갑니다...! 

매번 질문 받아주셔서 감사해용