[BOJ] 14926번: Not Equal

출처 : https://www.acmicpc.net/problem/14926

14926번: Not Equal

 

 

1. 문제 설명 

주어진 N개의 수가 모두 서로 다르다는 것은 기호 "!="를 통해 하나의 식으로 표현할 수 있다. 예를 들어 A, B, C가 모두 서로 다르다는 것은 논리식으로 (A != B) && (B != C) && (C != A) 로 쓸 수 있고, 이를 다음과 같이 한 줄로 표현하는 것을 A, B, C에 대한 "한 줄 표기법"이라고 부르기로 하자.

A != B != C != A

하지만 5개의 수 A, B, C, D, E가 모두 서로 다르다는 것을 다음처럼 표현하는 것은 올바른 한 줄 표기법이 아니다.

A != B != C != D != E

왜냐하면 5개의 수가 서로 다름을 나타내기 위해서는 10개의 쌍에 대해 서로 다름을 표현해야 하고, 이는 적어도 10개의 "!="를 필요로 하기 때문이다. 일반적으로 주어진 N개의 수가 모두 다름을 한 줄 표기법으로 표현하기 위해서는 적어도 C(N, 2)개의 "!="이 필요함이 알려져 있다(C(N, 2) : N개의 서로 다른 대상 중 2개를 뽑는 가짓수).

홀수 자연수 N이 주어졌을 때, N개의 수 a1, a2, …, aN에 대해 가능한 한 줄 표기법 중 가장 짧으면서 사전순으로 가장 앞에 오는 한 줄 표기법을 출력하는 프로그램을 작성하라. 단 이때 "!="은 공백으로 대신하기로 한다. 예를 들어 N = 3이 주어졌을 때 "a1 a2 a3 a1"는 정답으로 인정되지만, "a3 a1 a2 a3"는 사전순으로 앞의 표기법보다 뒤에 오기 때문에 올바른 한 줄 표기법이라도 정답으로 인정되지 않는다.

Hint : 한 줄 표기법에 최소로 필요한 "!="의 개수인 C(N, 2)는 Vertex가 N개인 완전 그래프의 Edge의 개수와 동일함을 고려해 보라.

 

 

2. 접근 방식 

처음에 문제를 이해하지 못하다가 예제를 따라서 구현해보니 오일러 경로를 다루는 문제였다. DFS로 구현을 하다가 인텔리제이에서 자꾸 해당 변수에 대해 뭐라뭐라 하는거였다.(그냥 변명이다) 그래서 아닌데 이게맞는데 하면서 바꿨다가 시간을 다써먹었다... (네 다음 변명) 무튼 다 구현하고나니 마지막 정점이 무조건 시작 정점으로 가야하는데 그에 따른 조건을 어떻게 줘야할 지 몰랐다. 처음 정점과 마지막 정점은 시작과 동시에 방문처리를 해줘야 한다는 힌트를 얻고 나서 푼 문제이다. (시작은 V1 -> Vn이고 마지막에는 Vn -> V1로 무조건 가야한다는 조건이다. 이게 오일러 경로라는 분류를 알고서 내가 발견해야 하는 것이였다... 나는 문어... 꿈을 꾸는 문어......)

 

 

오일러 경로(Eulerian Trail)은 그래프에 존재하는 모든 간선을 정확히 한 번씩 방문하는 연속된 경로를 의미한다. 시작점을 어느 지점으로 하느냐에 따라 몇몇의 간선에 도달하지 못할수도 있다.

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        visit = new boolean[N][N];
        graph = new int[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(i==j) visit[i][j] = true;
                graph[i][j] = j+1;
            }
        }
        visit[N-1][0] = true;
        visit[0][N-1] = true;
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static boolean[][] visit;
    static int[][] graph;
    static void rec_func(int x, int y) {
        visit[x][y] = true;
        visit[y][x] = true;
        System.out.print("a"+(x+1) + " ");
        for(int i=0; i<N; i++) {
            if(y==i) continue; // 자기자신이라면 continue
            if(!visit[y][i]) {
                rec_func(y,i);
            }
        }
    }
    public static void main(String[] args) throws IOException{
        input();
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(!visit[i][j]) {
                    rec_func(i,j);
                }
            }
        }

        System.out.print("a"+N+" "+"a"+1);
    }
}

 

 

4. 분석 및 시간복잡도 

시간복잡도 : O(V^2)