[2025 1학기 알고리즘 스터디] 남윤찬 #6주차

NP(Nondeterministic Polynomial time)

정의: 어떤 문제의 해답이 맞는지를 다항 시간 안에 검증할 수 있는 문제의 집합

더 쉽게 설명하면 직접 정답을 찾는 것을 오래 걸리고 어려우나, 주어진 것이 정답인지 판별하는 것은 빠르게 할 수 있는 문제이다.

(ex: 특정한 수가 어떤 소수들의 합으로 이루어져있는지 찾는 것 -> 오래걸리고 어려움 -> NP 아님

주어진 소수들의 합이 특정한 수인지 검증하는 것 -> 개빨리함 -> NP 맞음 (아마도?))

그 예시가 배송 최적화(어떻게 돌아야 가장 빠를까 → TSP), 일정짜기(모두가 만족하는 스케쥴이 가능한가) 등이 있다.

충분히 좋은 해답을 얼마나 빠르게 찾을 수 있나가 중요하다.

---

외판원 순회 2

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

public class Main {

    public static int n;
    public static int[][] map;
    public static boolean[] visited;
    public static int minCost = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visited = new boolean[n+1];

        for (int i = 0; i < n; i++) {
            String[] dummy = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(dummy[j]);
            }
        }

        visited[0] = true;
        backTrackingDfs(0,1,0);
        System.out.println(minCost);
    }

    public static void backTrackingDfs(int current, int count, int cost) {
        if (count == map.length) { // 모든 노드를 탐색하면 count가 노드의 개수가 되어있을 것이다.
            if (map[current][0] != 0) { // 그때 마지막 노드에서 처음 노드로 돌아갈 수 있으면
                minCost = Math.min(minCost, cost+map[current][0]); // 이전에 찾아냈던 비용과 비교하여 더 작은 비용을 기록
            }
            return;
        }

        for (int i = 1; i < n; i++) {
            if (!visited[i] && map[current][i] != 0) {
                visited[i] = true; // 다음으로 갈 i 노드 방문처리
                backTrackingDfs(i, count+1, cost + map[current][i]); // i에서 더 넘어갈 수 있는 경로를 재귀로 dfs
                visited[i] = false; // i를 거쳐 나아갈 수 있는 노드를 다 탐색한 뒤에는 다른 경로를 탐색할 때 이 노드를 방문할 수 있도록 미방문 처리
            }
        }
    }

}

문제에도 쓰여있듯 가장 대표적인 NP 문제인 TSP이다.

근데 TSP에도 두 가지가 있다

1. 최적화 문제
       최단 경로를 찾는 것 → NP 아님
2. 결정 문제
       총 이동 거리가 K 이하인 경로가 있나? → O/X 문제 → NP 문제임

이 문제는 결정 문제인 TSP이므로, 모든 경로를 돌아보고 최소 비용으로 순회할 수 있는 경우를 찾으면 된다. DFS로 백트래킹하며 경로를 찾아나서면 쉽게 알아낼 수 있다.

또한 순회 문제라서 시작점이 어디든 같은 경로에 대한 비용은 같아서 하나의 노드에서만 시작해도 문제를 해결할 수 있다. (1-2-3-4-1이든 2-3-4-1-2든 비용은 같음)

---

부분수열의 합

import java.util.Scanner;

public class Main {

    public static int n;
    public static int s;
    public static int[] seq;
    public static int answer = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        s = scanner.nextInt();

        seq = new int[n];

        for (int i = 0; i < n; i++) {
            seq[i] = scanner.nextInt();
        }

        dfs(0, 0);
        if (s == 0) System.out.println(answer-1);
        else System.out.println(answer);

    }

    public static void dfs(int depth, int sum) {
        if (depth == n) { // 끝까지 도달했을 때
            if (sum == s) answer++;
            return;
        }
        // 현재 노드를
        dfs(depth+1, sum + seq[depth]); // 포함하는 경우
        dfs(depth+1, sum); // 포함하지 않는 경우
    }

}

특정 값을 만족시키는 수열이 뭐가 있을까? → 너무 많음. 구할 수 Xx → NP가 아님

어떤 수열이 있을 때 특정 값을 만족시키는 경우의 수가 있을까? → NP 문제

 

이 문제를 풀려면 브루트포스를 해야할 거라고 생각은 했는데, 접근법을 잘 모르겠어서 찾아보았는데, 트리를 그리며 탐색해나가면 해결할 수 있다는 것을 알 수 있었습니다. 현재 층의 노드를 포함하는 경우, 아닌 경우로 나누어 이진트리를 그려나가고, depth가 수열의 길이와 같아졌을 때 그 합이 s와 같은지 판별하면 되는 문제였습니다.

간단하게 그림으로 보면 이런 느낌…입니다

---

N-Queen

import java.util.Scanner;

public class Main {

    public static int n;
    public static int[] board; // index: 열, value: 행
    public static int answer = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        board = new int[n];

        dfs(0);
        System.out.println(answer);
    }

    public static void dfs(int col) {
        if (col == n) { // col값이 n까지 도달했다는 것은 모든 퀸이 적절히 배치되었다는 것이다
            answer++;
            return;
        }

        for (int i = 0; i < n; i++) {
            board[col] = i;
            if (possible(col)) { // col열의 i행 좌표에 퀸이 배치될 수 있다면
                dfs(col+1); // 다음 열로 이동
            }
        }
        
    }

    public static boolean possible(int col) {
        for (int i = 0; i < col; i++) {
            if (board[col] == board[i] || // col번째와 i번째의 value가 같음 -> 이전의 퀸과 같은 행
                Math.abs(col-i) == Math.abs(board[col] - board[i])) { 
                    // 열 간의 차, 행 간의 차 각각의 절대값이 같음 -> i번째 열에 있는 퀸의 대각선에 있음
                    return false;
                }
        }
        return true;
    }

}

직접 퀸들의 배치를 찾기에는 어렵지만(조합 수가 N!에 가깝기 때문), 어떠한 배치를 주어주면 그것이 조건에 충족하는지 검증하는지는 어렵지 않기 때문에(가로, 세로, 대각선만 확인하면 된다) NP 문제에 해당한다.

이차원 배열을 그려 확인하는 방식을 해보려고 했으나, 검증의 과정이 길고 복잡해져서 다른 방법을 찾아보았는데, 일차원 배열을 활용하는 방법을 알 수 있었다. 배열의 index가 열, 그 값이 행이 된다(열과 행의 할당을 반대로 해도 가능하다). 그렇게 각 열의 어떤 행에 퀸을 배치하면 되는지 검증하며 배치해나가면 된다. 배치를 하는 과정은 dfs를 이용해 할 수 있었다.

퀸이 배치가 가능한지 검증하는 법은 더욱 간단했다. 배열에서 다른 인덱스의 값이 같으면 서로 같은 행에 배치하기에 불가능, 인덱스의 차의 절대값과 값의 차의 절대값이 같으면 대각선상에 위치해 있기에 불가능한 것으로 판별할 수 있었다.

이 방법은 가로, 세로, 대각선에 대해서만 판별하면 되어 가능한 방법이었다. 만약 다른 특수한 경우였다면 이차원 배열로 일일이 비교해야해 더 어려웠을 수도 있을 것 같다.