๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\๋ฐฑํŠธ๋ž˜ํ‚น

๋ฐฑ์ค€ 9663๋ฒˆ : N-Queen (JAVA) ๋ฌธ์ œ ํ’€์ด

2020. 12. 22. 18:00
๋ชฉ์ฐจ
  1. ๋ฌธ์ œ ๋ถ„์„
  2. ๋‚ด๊ฐ€ ์ƒ๊ฐํ•ด๋‚ธ ํ’€์ด
๋ฐ˜์‘ํ˜•

www.acmicpc.net/problem/9663

 

9663๋ฒˆ: N-Queen

N-Queen ๋ฌธ์ œ๋Š” ํฌ๊ธฐ๊ฐ€ N ร— N์ธ ์ฒด์ŠคํŒ ์œ„์— ํ€ธ N๊ฐœ๋ฅผ ์„œ๋กœ ๊ณต๊ฒฉํ•  ์ˆ˜ ์—†๊ฒŒ ๋†“๋Š” ๋ฌธ์ œ์ด๋‹ค. N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ํ€ธ์„ ๋†“๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

www.acmicpc.net

 


 

๋ฌธ์ œ ๋ถ„์„


ํ€ธ์˜ ๊ณต๊ฒฉ ๋ฐฉํ–ฅ

ํ€ธ์˜ ํŠน์„ฑ์ƒ ํ•œ์ค„์— ํ•˜๋‚˜์”ฉ ๋ฐ–์— ๋‘˜์ˆ˜๊ฐ€ ์—†๊ฒŒ ๋œ๋‹ค.

์ผ๋‹จ ๋จผ์ € N์ด 4๋ผ๊ณ  ๊ฐ€์ •ํ•˜๊ณ , ํ€ธ์„ ๋ฐฐ์น˜ํ•ด๋ณด์ž.

4 X 4 ์ฒด์ŠคํŒ์— [0][0] ์œ„์น˜์— 1๋ฒˆ์งธ ํ€ธ์„ ๋‘”๋‹ค๊ณ  ํ•˜๋ฉด,

1๋ฒˆ์งธ ํ€ธ, [0][0]์— ๋‘๋Š” ๊ฒฝ์šฐ

๋‹ค๋ฅธ ํ€ธ์„ ๋ฐฐ์น˜ํ•˜์ง€ ๋ชปํ•˜๋Š” ์œ„์น˜(ํ€ธ์˜ ๊ณต๊ฒฉ์„ ๋ฐ›์„ ์ˆ˜ ์žˆ๋Š” ๊ณณ)์€ ์œ„์˜ ๊ทธ๋ฆผ ์ฒ˜๋Ÿผ ๋œ๋‹ค.

๊ทธ๋Ÿฌ๋ฉด 2๋ฒˆ์งธ ํ€ธ์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š” ๊ณณ์€, [1][2] ์™€ [1][3] ๋‘ ๊ฐ€์ง€

์ด๋ ‡๊ฒŒ [1][2]์™€ [1][3]์— ๋‘ ๊ณณ์— ๋†“์„ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค.

[1][2]์— ๋†“์•˜์„ ๊ฒฝ์šฐ์—๋Š”, ๋‹ค์Œ ์ค„์— ๋‘˜ ์ˆ˜๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์— ํ•ด๋‹ต์ด ๋  ์ˆ˜๊ฐ€ ์—†๊ณ ,

[1][3]์— ๋†“์•˜์„ ๊ฒฝ์šฐ์—๋Š”, [2][1]์— ๋‘˜ ์ˆ˜๊ฐ€ ์žˆ๊ฒŒ ๋˜์„œ ๋‹ค์‹œ ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๊ฒŒ ๋œ๋‹ค.

3๋ฒˆ์งธ ํ€ธ์„ [2][1]์— ํ€ธ์„ ๋‘๋Š” ๊ฒฝ์šฐ

์ด๋ ‡๊ฒŒ ๋˜๋ฉด, 4๋ฒˆ์งธ ํ€ธ์„ ๋‘˜ ๊ณต๊ฐ„์ด ์—†๊ธฐ ๋•Œ๋ฌธ์— ๋‹ต์ด ๋  ์ˆ˜๊ฐ€ ์—†๋‹ค.

์ด์ œ ์ด ๊ณผ์ •๋“ค์„ ๋ฐ˜๋ณตํ•˜๋ฉด ๋œ๋‹ค.


 

๋‚ด๊ฐ€ ์ƒ๊ฐํ•ด๋‚ธ ํ’€์ด


์ผ๋‹จ ํ€ธ์˜ ์œ„์น˜๋ฅผ ์ €์žฅํ•œ ์ด์ฐจ์› ๋ฐฐ์—ด int[ ][ ] ์™€, ๋ฐฉ๋ฌธ์—ฌ๋ถ€๋ฅผ ์ €์žฅ ํ•  ์ด์ฐจ์› ๋ฐฐ์—ด boolean[ ][ ] ๋‘๊ฐœ๋ฅผ ์„ ์–ธํ–ˆ๋‹ค.

public class Main {
    static int[][] queen;        // ํ€ธ์˜ ์œ„์น˜ ํ‘œ์‹œ
        static boolean[][] visit;    // ํ€ธ์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š”์ง€

        ..
}

N๊ณผ M ๋ฌธ์ œ ์ฒ˜๋Ÿผ, ๋ฐฑํŠธ๋ž˜ํ‚น์„ ๊ตฌํ˜„ํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

public class Main {
    static int[][] queen;    // ํ€ธ์˜ ์œ„์น˜ ํ‘œ์‹œ
    static boolean[][] visit;    // ํ€ธ์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š”์ง€
    static int N;
    static int result = 0;

    static void dfs(int n) {
        if (n == N) {
            //arr = new int[N][N]; // ์ดˆ๊ธฐํ™”
            result++;
            return;
        }


        for (int j = 0; j < N; j++) {

            if (!visit[n][j]) {
                visit[n][j] = true;
                arr[n][j] = 1;

                /* ํ€ธ์˜ ๊ณต๊ฒฉ๋ฐฉํ–ฅ ์ฒดํฌ */

                dfs(n + 1);

                /* ์ด์ „ ์ƒํƒœ๋กœ ๋Œ๋ ค ๋†“๊ธฐ! */
            }
        }
    }

๋ฐฑํŠธ๋ž˜ํ‚น ๊ธฐ๋ณธ ๊ตฌ์กฐ๋ฅผ ์‚ดํŽด๋ณด์ž๋ฉด

์žฌ๊ท€ํ•จ์ˆ˜์˜ ์ข…๋ฃŒ์‹œ์ ์€,

n์ด M๊ณผ ๊ฐ™์•„์ง€๋Š” ์‹œ์ ์—๋Š” M๊ฐœ์˜ ํ€ธ์„ ๋‘”๊ฒƒ์ด๋ผ๊ณ  ํŒ๋‹จํ•˜์—ฌ result์˜ ๊ฐ’์„ ์ฆ๊ฐ€ ์‹œ์ผœ์ฃผ๋ฉด ๋œ๋‹ค.

  • ํ€ธ์˜ ๊ณต๊ฒฉ๋ฐฉํ–ฅ์„ ์ฒดํฌ
  • ์žฌ๊ท€ ํ˜ธ์ถœ์„ ํ•œ ๋‹ค์Œ, ๋‹ค๋ฅธ ๊ฒฝ์šฐ๋ฅผ ๋‹ค ํƒ์ƒ‰ํ•˜๊ณ  ๋‚œ ๋’ค, ํ˜„์žฌ์˜ ํ€ธ ๊ณต๊ฒฉ์œ„์น˜๋ฅผ ๋‹ค์‹œ ๋˜๋Œ๋ ค ๋†“๋Š”๋‹ค.

์œ„์— ๊ณผ์ •์„ ๋ฐ˜๋ณต์‹œ์ผœ ์ฃผ๋ฉด ๋œ๋‹ค.


ํ€ธ์˜ ๊ณต๊ฒฉ๋ฐฉํ–ฅ ์ฒดํฌ

  1. ํ€ธ์˜ ์•„๋ž˜ ๋ฐฉํ–ฅ ๊ณต๊ฒฉ ( for๋ฌธ์„ ์ด์šฉํ•ด ์•ž ์ธ๋ฑ์Šค๋งŒ ์ฆ๊ฐ€์‹œ์ผœ ์ฒดํฌํ•ด์ค€๋‹ค.)
  2. ํ€ธ์˜ ์™ผ์ชฝ ์•„๋ž˜ ๋Œ€๊ฐ์„  ๋ฐฉํ–ฅ ( [+1] [-1] ์„ ์‹œ์ผœ์ฃผ๋ฉด์„œ ๋ฒฝ์— ๋ถ€๋”ชํžˆ๋ฉด ์ข…๋ฃŒ ์‹œ์ผœ์ค€๋‹ค.)
  3. ํ€ธ์˜ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜ ๋Œ€๊ฐ์„  ๋ฐฉํ–ฅ ( [+1] [+1] ์„ ์‹œ์ผœ์ฃผ๋ฉด์„œ ๋ฒฝ์— ๋ถ€๋”ชํžˆ๋ฉด ์ข…๋ฃŒ ์‹œ์ผœ์ค€๋‹ค.)

(์–‘ ์˜†๊ณผ, ์œ„์ชฝ ๋ฐฉํ–ฅ์—๋Š” ์ฒดํฌ๋ฅผ ํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค.)

์ฝ”๋“œ

public static void check_queen_Atack(int a, int b) {
    /* ์•„๋ž˜ ๋ฐฉํ–ฅ */
    for (int i = a; i < N; i++) {
        visit[i][b] = true;
    }
    /* ์™ผ์ชฝ ๋Œ€๊ฐ์„  */
    int c = a;
    int d = b;
    while (0 <= d && d < N & 0 <= c & c < N) {
        visit[c++][d--] = true;
    }
    /* ์˜ค๋ฅธ์ชฝ ๋Œ€๊ฐ์„  */
    while ((0 <= a && a < N & (0 <= b && b < N))) {
        visit[a++][b++] = true;
    }
}

 


์ด์ „ ์ƒํƒœ๋กœ ๋˜๋Œ๋ฆฌ๊ธฐ

์ด์ „ ์ƒํƒœ๋กœ ๋˜๋Œ๋ฆฌ๊ธฐ ์œ„ํ•ด์„œ๋Š”, ํ€ธ์˜ ์œ„์น˜๋ฅผ ํ‘œ์‹œํ•ด์ฃผ๋Š”๊ฒŒ ์ค‘์š”ํ•˜๋‹ค.

์žฌ๊ท€ ํ•จ์ˆ˜ ์ฝ”๋“œ ์ค‘ ์‚ดํŽด๋ณด๋ฉด,

public static void ์žฌ๊ท€ํ•จ์ˆ˜(int n) {

    //    ์ƒ๋žต

    for(int j=0; j < N; j++) {
        if( !visit[n][j] ) {
            visit[n][j] = true;    // ํ•ด๋‹น ์ธ๋ฑ์Šค ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ
            queen[n][j] = 1;     // ํ€ธ ๋†“์€ ์œ„์น˜ ๊ธฐ์–ต

            /* ํ€ธ์˜ ๊ณต๊ฒฉ ๋ฐฉํ–ฅ ์ฒดํฌ */

            ์žฌ๊ท€ํ•จ์ˆ˜(n + 1);    // ๋‹ค์Œ ํ€ธ ๋ฐฐ์น˜

            /* ๋‚˜๋จธ์ง€ ๋ฐฉ๋ฒ•์˜ ํ€ธ ๋ฐฐ์น˜๊ฐ€ ๋๋‚ฌ๋‹ค๋Š” ์˜๋ฏธ์ด๋ฏ€๋กœ, 
                ๋‹ค์‹œ ์›์ƒ๋ณต๊ท€ ์‹œ์ผœ ์ค€๋‹ค. */

            queen[n][j] = 0;    // ๋‹ค์‹œ ํ€ธ์„ ๋นผ๋„๋ก ํ•œ๋‹ค.

            /* ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ ํ–ˆ๋˜ ๋ฐฐ์—ด ์ดˆ๊ธฐํ™” */
            for(int p=0; p < N; p++) {
                for(int q=0; q < N; q++) {
                    if(queen[p][q] == 1) {
                        // ํ€ธ์„ ๋‘์—ˆ๋˜ ๊ณณ์„ ๋‹ค์‹œ ์ฒดํฌ
                    }
                }
            }
        }
    }
}

 

 

์ „์ฒด ์ฝ”๋“œ


 

import java.util.Scanner;

public class Main {
    static boolean[][] visit;
    static int[][] arr;
    static int N;
    static int result = 0;

    public static void dfs(int n) {
        if (n == N) {
            result++;
            return;
        }
        
        for (int j = 0; j < N; j++) {
            if (!visit[n][j]) {
                visit[n][j] = true;
                arr[n][j] = 1;

                /* ํ€ธ์˜ ๊ณต๊ฒฉ๋ฐฉํ–ฅ ์ฒดํฌ */
                check_queen_Atack(n, j);

                dfs(n + 1);

                /* ์ด์ „ ์ƒํƒœ๋กœ ๋Œ์•„๊ฐ€๊ธฐ */
                arr[n][j] = 0;	// ํ€ธ์„ ๋นผ๊ณ ,
                init_visit();	// ์ดˆ๊ธฐํ™”๋ฅผ ์‹œํ‚จ๋’ค
                
                /* ์ด์ „์— ๋‘์—ˆ๋˜ ํ€ธ์˜ ์œ„์น˜ ๋ณต์› */
                for (int i = 0; i < N; i++) {
                    for (int p = 0; p < N; p++) {
                        if (arr[i][p] == 1)
                            check_queen_Atack(i, p);
                    }
                }
            }
        }
    }

	/* ํ€ธ์˜ ๊ณต๊ฒฉ ๋ฐฉํ–ฅ ํ‘œ์‹œํ•˜๋Š” ๋ฉ”์†Œ๋“œ */
    public static void check_queen_Atack(int a, int b) {
        /* ์•„๋ž˜ ๋ฐฉํ–ฅ */
        for (int i = a; i < N; i++) {
            visit[i][b] = true;
        }
        /* ์™ผ์ชฝ ๋Œ€๊ฐ์„  */
        int c = a;
        int d = b;
        while (0 <= d && d < N & 0 <= c & c < N) {
            visit[c++][d--] = true;
        }
        /* ์˜ค๋ฅธ์ชฝ ๋Œ€๊ฐ์„  */
        while ((0 <= a && a < N & (0 <= b && b < N))) {
            visit[a++][b++] = true;
        }
    }

	/* ์ฒด์ŠคํŒ ์ดˆ๊ธฐํ™” ์‹œํ‚ค๋Š” ๋ฉ”์†Œ๋“œ */
    public static void init_visit() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visit[i][j] = false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        visit = new boolean[N][N];
        arr = new int[N][N];
        dfs(0);
        System.out.println(result);
    }
}

๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)
  1. ๋ฌธ์ œ ๋ถ„์„
  2. ๋‚ด๊ฐ€ ์ƒ๊ฐํ•ด๋‚ธ ํ’€์ด
'๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ/BAEKJOON\๋ฐฑํŠธ๋ž˜ํ‚น' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • ๋ฐฑ์ค€ 14889๋ฒˆ : ์Šคํƒ€ํŠธ์™€ ๋งํฌ (JAVA) ๋ฌธ์ œ ํ’€์ด
  • ๋ฐฑ์ค€ 14888๋ฒˆ : ์—ฐ์‚ฐ์ž ๋ผ์›Œ๋„ฃ๊ธฐ (JAVA) ๋ฌธ์ œ ํ’€์ด
  • ๋ฐฑ์ค€ 15650๋ฒˆ : N๊ณผ M(2) (JAVA) ๋ฌธ์ œ ํ’€์ด
  • ๋ฐฑ์ค€ 15649๋ฒˆ : N๊ณผ M(1) (JAVA) ๋ฌธ์ œ ํ’€์ด
iseunghan
iseunghan
๊พธ์ค€ํ•˜๊ฒŒ ์—ด์‹ฌํžˆ..
iseunghan
iseunghan

๊ณต์ง€์‚ฌํ•ญ

  • ์–ด์ œ๋ณด๋‹ค ๋‚˜์€ ์˜ค๋Š˜์ด ๋˜๊ธฐ ์œ„ํ•ด ๐Ÿ”ฅ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (261)
    • ๐Ÿ’ Spring (14)
      • ๊ฐœ๋… ๋ฐ ์ดํ•ด (2)
      • Spring ํ•ต์‹ฌ ๊ธฐ์ˆ  (24)
      • Spring REST API (8)
      • Spring MVC, DB ์ ‘๊ทผ ๊ธฐ์ˆ  (7)
      • Spring Security (23)
      • Spring in Action (1)
    • ๐ŸŒป JAVA (84)
      • ์ž๋ฐ” ORM ํ‘œ์ค€ JPA ํ”„๋กœ๊ทธ๋ž˜๋ฐ (20)
      • ์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ž๋ฃŒ๊ตฌ์กฐ (13)
      • ๋””์ž์ธ ํŒจํ„ด (7)
      • ์ •๋ฆฌ์ •๋ฆฌ์ •๋ฆฌ (43)
      • JUnit (1)
    • ๐Ÿ”– Snippets (3)
      • Javascript (3)
    • โš™๏ธ Devops (22)
      • โ› Git (11)
      • ๐Ÿณ Docker (6)
      • ๐Ÿง Linux (3)
      • ๐ŸŒˆ Jenkins (1)
      • ๐Ÿ“ฌ Kafka (1)
    • ๐Ÿ’ฌ ETC.. (4)
      • ๐Ÿ’ป macOS (2)
    • ๐ŸŒง๏ธ ORM (2)
      • JPA (2)
    • ๐Ÿ Python (2)
    • ๐Ÿ“š Databases (15)
      • ์˜ค๋ผํด๋กœ ๋ฐฐ์šฐ๋Š” ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ๊ฐœ๋ก ๊ณผ ์‹ค์Šต(2ํŒ) (3)
      • RealMySQL 8.0 (8)
    • ๐Ÿ”ฅ Computer Science (5)
      • ๐Ÿ“ก ๋„คํŠธ์›Œํฌ (5)
    • ๐Ÿท๏ธ ํ˜‘์—… (1)
    • ๐Ÿ“œ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ (38)
      • BAEKJOON\์ˆ˜ํ•™ 1, ์ˆ˜ํ•™ 2 (8)
      • BAEKJOON\์žฌ๊ท€ (5)
      • BAEKJOON\๋ธŒ๋ฃจํŠธ ํฌ์Šค (3)
      • BAEKJOON\์ •๋ ฌ (1)
      • BAEKJOON\๋ฐฑํŠธ๋ž˜ํ‚น (5)
      • BAEKJOON\BFS, DFS (6)
      • BAEKJOON\์ด๋ถ„ํƒ์ƒ‰ (1)
      • BAEKJOON\๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ (9)
      • BAEKJOON\๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜ (0)
    • โœจ ISEUNGHAN (1)

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
iseunghan
๋ฐฑ์ค€ 9663๋ฒˆ : N-Queen (JAVA) ๋ฌธ์ œ ํ’€์ด
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๊ฐœ์ธ์ •๋ณด

  • ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ
  • ํฌ๋Ÿผ
  • ๋กœ๊ทธ์ธ

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.