순열 | 재귀함수, visited[]

import java.util.Arrays;

public class 순열_visited {

	static int[] nums;
	static boolean[] visited;
	static int[] result;
	static int N;
	public static void main(String[] args) {

		nums = new int[] {1,2,3};
		N = nums.length;
		result = new int[N];
		visited = new boolean[N];
		
		perm(0);
	}

	
	
	public static void perm(int idx) {
		if(idx == N) {
			System.out.println(Arrays.toString(result));
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(visited[i]) continue;
			
			result[idx] = nums[i];
			visited[i] = true;
			perm(idx+1);
			visited[i] = false;
		}	
	}
}

---

✔알고리즘 문제를 풀 땐, 수학의 순열만을 생각하는 것이 아니라 문제 상황 속에서 순열의 논리가 적용이 되는지, 조합 또는 부분집합의 논리가 적용이 되는지를 따져보는 것

---

📝예제 문제. swea 2806 N-Queen

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 재귀함수 + 순열
public class swea2806 {
 
    static int[][] board;
    static int n;
    static int cnt;
    static boolean[] check;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());
            board = new int[n][n];
            check = new boolean[n];
            cnt=0;
             
            put(0, 0);
            System.out.println("#" + t + " " + cnt);
        }
 
    } // main
 
    static void put(int Q, int row) {
    	if (Q == n) {
    		// 모든 퀸을 판에 놓았다.
    		cnt++;
    		return;
    	}

        for(int j=0; j<n; j++) {
        	if(deltaCheck(row, j)) {
		        board[row][j] = 1;
		        check[row] = true;
		        put(Q + 1, row+1);
		        board[row][j] = 0;
		        check[row] = false;
        	}
        }
    }
    
    static boolean deltaCheck(int i, int j) {
        int r = i;
        int c = j;
        
        // 열 검사
        while (r > 0) {
            if (board[--r][j] == 1)
                return false;
        }
 
        // 오른쪽 대각선 검사
        r = i;
        while (r > 0 && c < n - 1) {
            if (board[--r][++c] == 1)
                return false;
        }
 
        // 왼쪽 대각선 검사
        r = i;
        c = j;
        while (r > 0 && c > 0) {
            if (board[--r][--c] == 1)
                return false;
        }
 
        return true;
    }
}

트리로 상상하기!!

row=2일동안 col 1부터 특정 col까지 검사를 하는데, 특정 col이 조건에 맞지 않다면 돌아나와서 다음 col을 검사하고
row=2일 때 모든 col을 검사해도 조건에 맞는 것이 나오지 않는다면 돌아나와서 row=3을 검사한다.