[SWEA] 5643 키 순서 - JAVA

1. 문제

BOJ 2458 키 순서와 동일한 문제다.

SW Expert Academy

 

2458번: 키 순서

 

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다. 

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다. 

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

---

2. 풀이

메인

1.  N크기가 500개라서 인접행렬로도 풀 수 있다고 판단했다. 따라서 인접행렬 map에 들어오는 수 순서대로 인덱스 접근해 연결처리했다. 먼저 들어오는 수 a가 나중에 들어오는 수 b보다 작고, 이 때 a->b이므로 map[a][b]에만 true로 변경했다.

2.  출력할 결과 result를 0으로 초기화시키고, 1부터 N까지(번호가 1부터 시작한다) i를 반복한다.

3.  2를 반복할 때, 방문배열을 초기화시킨 후 find(i)를 호출해야한다.

4.  find(i)의 결과가 true라면 result+1 한다.

5.  result를 출력한다.

static Queue<int[]> queue = new ArrayDeque<>();
static boolean[] visited;
static int N;
static boolean[][] map;

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st;
   StringBuilder sb = new StringBuilder();
   int T = Integer.parseInt(in.readLine());
   for (int tc = 1; tc <= T; tc++) {
      N = Integer.parseInt(in.readLine());
      int M = Integer.parseInt(in.readLine());
      map = new boolean[N + 1][N + 1];

      for (int i = 0; i < M; i++) {
         st = new StringTokenizer(in.readLine());
         map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = true;
      }

      int result = 0;
      for (int i = 1; i <= N; i++) {
         visited = new boolean[N + 1];
         if (find(i)) ++result;
      }

      sb.append('#').append(tc).append(' ').append(result).append('\n');
   }
   System.out.print(sb);
}

 

탐색

1.  시작학생보다 큰 학생은 그 학생보다 더 큰 학생들만 시작학생보다 확실히 크다. (연결된 학생들 기준)

2.  시작학생보다 작은 학생은 그 학생보다 더 작은 학생들만 시작학생보다 확실히 작다.

3.  따라서 시작학생 제외하고 큰 학생은 더 큰 학생들만, 작은 학생은 더 작은 학생들만 셀 수 있다.

4.  1~3을 구분하기 위해 시작학생은 [1]칸에 0을 넣고 큰 학생은 [1]칸에 1, 작은 학생은 [1]칸에 -1을 넣었다.

5.  큰 지 작은 지 상관없이 [0]칸에는 자신의 번호를 넣는다.

6.  큐는 다음과 같이 동작한다.

    6-1) 큐의 맨 앞 수를 뽑는다(pos). 

    6-2) 학생 수를 한 명 증가시킨다.

    6-3) 이미 뽑은 적 있다면 (visited[i]==true) 넘긴다.

    6-4) 만약 pos가 시작학생보다 크다면 map[pos학생번호][i]가 연결되어있는지 확인한다.

    6-5) 만약 pos가 시작학생보다 작다면 map[i][pos학생번호]가 연결되어있는지 확인한다.

    6-6) 만약 pos가 시작학생이라면 6-4, 6-5 모두 확인한다.

7.  큐가 비었을 때의 cnt를 확인한다. cnt가 총 학생수와 동일하다면 시작학생은 키 순서를 정확히 알 수 있는 학생이다. 따라서 true를 반환한다. 그렇지 않다면 false를 리턴한다.

private static boolean find(int n) {
   int cnt = 0;
   int[] pos = {n, 0};//시작지점은 큰거 작은거 다 들어와야 함.
   queue.offer(pos);
   visited[n] = true;

   while (!queue.isEmpty()) {
      pos = queue.poll();
      cnt++;
      for (int i = 1; i <= N; i++) {
         if (visited[i]) continue;
         if (pos[1] >= 0 && map[pos[0]][i]) {//나보다 큰
            queue.offer(new int[]{i, 1});
            visited[i] = true;
         }
         if (pos[1] <= 0 && map[i][pos[0]]) {//나보다 작은
            queue.offer(new int[]{i, -1});
            visited[i] = true;
         }
      }
   }

   return cnt == N;
}

---

3. 결과