์—ฐ๊ตฌ์†Œ(14502)

์ด ๋ฌธ์ œ๋ฅผ ํ’€๋•Œ์˜ ๋ฌธ์ œ์ 

  1. ์ด๋Ÿฌํ•œ ๋ฌธ์ œ๋Š” ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ์ฐพ๊ธฐ ์ด์ „์— ๊ฐ€์žฅ ๋จผ์ € ๋ธŒ๋ฃจํŠธํฌ์Šค๋ฅผ ์‹œ๋„ํ•˜๊ธฐ์— ์•„์ฃผ ์ข‹์Œ์—๋„ ๋ถˆ๊ตฌํ•˜๊ณ  ์ž˜ ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค. ๋”ฑ ๋ณด๊ธฐ์— ๋„ˆ๋ฌด ๋ฌด์‹ํ•ด๋ณด์ธ๋Š” ๋ฐฉ๋ฒ•์ด๋ผ์„œ ์‹œ๋„์กฐ์ฐจ ํ”ผํ•œ๋‹ค. ์ตœ์•…์˜ ๊ฒฝ์šฐ ์‹œ๊ฐ„๋ณต์žก๋„์™€ ๋Œ€๋žต์ ์œผ๋กœ ๊ณ„์‚ฐํ•˜๊ณ  ์ œํ•œ์‹œ๊ฐ„์„ ๋„˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ ๋ง์„ค์ด์ง€ ๋ง๊ณ  ์‚ฌ์šฉํ•˜์ž.

    ex) ์ตœ์•…์˜ ๊ฒฝ์šฐ 8^8(์•ฝ 1.6์ฒœ๋งŒ) ์ •๋„๋ผ ์ถฉ๋ถ„ํžˆ ์‚ฌ์šฉํ•ด๋„ ๋œ๋‹ค.
  2. ์ž‘์„ฑํ•  ์ฝ”๋“œ๋ฅผ ๋ฏธ๋ค„๋‘์ง€ ๋ง์ž. ๋งŒ์•ฝ ๋ฏธ๋ค„๋‘ฌ์•ผํ•œ๋‹ค๋ฉด ์•„๋ž˜์™€ ๊ฐ™์ด ์ฃผ์„์„ ๋‹ฌ์•„๋‘์ž.

    // TODO : queue์—์„œ front๊ฐ’์„ ๋ณ„๋„๋กœ ๋ณ€์ˆ˜์— ์ €์žฅ, ๊ทธ ๋‹ค์Œ popํ•ด์•ผํ•œ๋‹ค.
    // (์ดํ•˜๋Š” ์ฝ”๋“œ๋กœ ๋ฐ”๊พผ ๊ฒฝ์šฐ)
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
  3. ์ธ๋ฑ์Šค๋ฅผ ์ œํ•œํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ ์˜ฌ๋ฐ”๋ฅธ ๋‹ต์ด ๋‚˜์˜ค์ง€ ์•Š์•˜๋˜ ์ด์œ ๋Š”?

    ๊ฐœ์„  ์ด์ „ ๋ฐฉ๋ฒ•

    ๋งค๋ฒˆ 0,0 ๋ถ€ํ„ฐ ๋ฃจํ”„๋ฅผ ๋Œ๊ธฐ ๋•Œ๋ฌธ์— ์ฝ”๋“œ๊ฐ€ ๋ถˆํ•„์š”ํ•˜๊ฒŒ ๋ฐ˜๋ณต๋œ๋‹ค.

    void solve(int count){
        /* ์ƒ๋žต */
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if(map[i][j] == 0){
                    map[i][j] = 1;
                    solve(i,j,count + 1);
                    map[i][j] = 0;
                }
            }
        }
        return;
    }

    ๋”ฐ๋ผ์„œ ์ด์ „ ์ขŒํ‘œ์—์„œ ๋ฃจํ”„๋ฅผ ์‹œ์ž‘ํ•˜์—ฌ ๋ฐ˜๋ณต์„ ๋ฐฉ์ง€ํ•˜๋ ค๊ณ  ์‹œ๋„ํ–ˆ๋‹ค. ํ•˜์ง€๋งŒ ์ด ์ฝ”๋“œ๋Š” ๋ฃจํ”„๋ฅผ ํ•œ๋ฒˆ ๋ˆ ์ดํ›„์—๋„ x,y๊ฐ€ ๊ณ ์ •์ด๊ธฐ ๋•Œ๋ฌธ์— ์˜ฌ๋ฐ”๋ฅธ ๋‹ต์ด ๋‚˜์˜ค์ง€ ์•Š์•˜๋‹ค.

    void solve(int x, int y, int count){
        /* ์ƒ๋žต */
        for (int i = x; i < n; i++){
            for (int j = y; j < m; j++){ // y๊ฐ€ ๋ฃจํ”„๋ฅผ ๋ˆ ์ดํ›„์—๋„ ๊ณ ์ •
                if(map[i][j] == 0){
                    map[i][j] = 1;
                    solve(i,j,count + 1);
                    map[i][j] = 0;
                }
            }
        }
        return;
    }

    ๋ฌธ์ œ์ ์„ ํ•ด๊ฒฐํ•œ ๊ฐœ์„ ๋œ ์ฝ”๋“œ

    void solve(int x, int y, int count){
        /* ์ƒ๋žต */
        for (int i = x; i < n; i++){
            for (int j = y; j < m; j++){
                if(map[i][j] == 0){
                    map[i][j] = 1;
                    solve(i,j,count + 1);
                    map[i][j] = 0;
                }
            }
            y = 0; // ๋ฃจํ”„๋ฅผ ํ•œ๋ฒˆ ๋Œ์•˜๋‹ค๋ฉด y๊ฐ’์„ 0์œผ๋กœ ์ดˆ๊ธฐํ™” ํ•ด์ค˜์•ผํ•œ๋‹ค.
        }
        return;
    }

    ์ด๋Ÿฌํ•œ ๊ธฐ์ดˆ์ ์ธ ์‹ค์ˆ˜๋ฅผ ์ค„์—ฌ์•ผ ํ•œ๋‹ค.