백준 2623 음악프로그램 [JAVA]

백준 2623 음악프로그램 [JAVA]

728x90

solved.ac = 골드 2

https://www.acmicpc.net/problem/2623

1. 접근

문제 속 입력을 그래프로 만들어 위상 정렬하는 문제입니다.

처음에는 input으로 어떻게 그래프를 만들어야 하나 고민이 많았던 문젠데 예제 입력을 그림으로 그려보니 바로 이해가 되서 풀었던 문제입니다.

예제 입력의 두 번째 줄부터 간선 정보라 생각하고 그래프로 그려보면 다음과 같습니다.

입력 받은대로 단방향 그래프를 그리고 자신에게 향하는 간선이 없는 노드를 차례대로 삽입하면 문제의 정답을 구할 수 있습니다.

단, 위상 정렬은 사이클이 발생하지 않는 DAG 형태이어야 하는데 문제를 보면 예외 상황도 주어집니다.

따라서 정답 리스트를 삽입 후 출력하기 전에 노드 수 만큼 삽입이 되었는지 확인 후 출력해야 합니다.

2. 풀이

변수 세팅

static int N, M; static int[] indeg; static ArrayList[] graph; static ArrayList answer = new ArrayList<>(); public static void main(String[] args) throws IOException { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); indeg = new int[N + 1]; graph = new ArrayList[N + 1]; for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>(); for (int i = 1; i <= M; i++) { st = new StringTokenizer(br.readLine()); int cnt = Integer.parseInt(st.nextToken()), x = Integer.parseInt(st.nextToken()); // 간선 정보가 따로따로 입력된게 아닌 한 줄로 쭉 나와있으니 // x를 바꿔가며 그래프를 생성한다. for (int j = 1; j < cnt; j++) { int y = Integer.parseInt(st.nextToken()); graph[x].add(y); indeg[y]++; // y로 가는 간선 개수 추가 x = y; } } solution(); }

탐색 및 정답 출력

static void solution() { Deque queue = new LinkedList<>(); // 들어오는 간선이 없는 노드를 추가한다. for (int i = 1; i <= N; i++) { if (indeg[i] == 0) queue.add(i); } while(!queue.isEmpty()) { int x = queue.poll(); answer.add(x); for (int y : graph[x]) { indeg[y]--; // 방문했으니 들어가는 간선이 하나 줄어든다. if (indeg[y] == 0) queue.add(y); } } // 사이즈가 N개가 아니다 == 모든 가수의 순서를 정하지 못했다! if(answer.size() != N) System.out.println(0); else { for (int x : answer) sb.append(x).append('

'); System.out.println(sb.toString()); } }

3. 전체 코드

728x90

from http://dhbang.tistory.com/44 by ccl(A) rewrite - 2021-12-28 18:00:53