🥇 [Baekjoon / Java] 2252. 줄 세우기

이하얀·2024년 6월 7일

2252 2252번 Java baekjoon 골드3 골드III 백엔드 백준 알고리즘 자바 줄 세우기

🐣 백준

목록 보기

19/33

문제 설명

💡 Info

난이도 : 골드 3
시간 제한 : 2초
메모리 제한 : 128MB
백준 링크: https://www.acmicpc.net/problem/2252
풀이 링크(GitHub): hayannn/CodingTest_Java/백준/Gold/2252. 줄 세우기

내용

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

📥입력 조건

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다.
M은 키를 비교한 횟수이다.
다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.
학생들의 번호는 1번부터 N번이다.
```
3 2
1 3
2 3
```
```
4 2
4 2
3 1
```

📤출력 조건

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.
```
1 2 3
```
```
4 2 3 1
```

문제 이해

N : 학생 수
M : 키 비교 횟수 = 즉, 교환 횟수
DFS 진행(SWEA 1244번 최대상금과 비슷)

알고리즘

실제 풀이 시간 : 14분

입력
- 학생 수 N 입력받기
- 비교 횟수 M 입력받기
- 2차원 배열 arr 입력받기
계산
- dfs 계산하기
출력
- 결과 result 출력하기
별도 메서드
- DFS 진행
  - 방문한 노드는 true로 변경
  - 노드 출력
  - 만약 노드가 arr.length에 다다랐다면 → return;
  - for문
    - if(arr[V][i] == 1 && !visited[i]) dfs(i);

import java.util.*;

public class Main {
    static int N;
    static int M;
    static int[][] arr;
    static boolean[] visited;

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

        N = sc.nextInt();
        M = sc.nextInt();

        sc.nextLine();

        arr = new int[N + 1][N + 1];
        for (int i = 0; i < M; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            arr[from][to] = 1;
            arr[to][from] = 1;
        }

        visited = new boolean[N + 1];

        dfs(1); // 정점이 1부터 시작함

        System.out.println();
    }

    public static void dfs(int V) {
        visited[V] = true;

        System.out.print(V + " ");

        for (int i = 1; i <= N; i++) {
            if (arr[V][i] == 1 && !visited[i])
                dfs(i);
        }
    }
}

오답 체크

DFS로 진행하니, 결과 값이 1 2 3이 아닌 1 3 2가 나옴!!
- BFS로 변경

//before
    public static void dfs(int V) {
        visited[V] = true;

        System.out.print(V + " ");

        for (int i = 1; i <= N; i++) {
            if (arr[V][i] == 1 && !visited[i])
                dfs(i);
        }
    }

//after

또한, 메모리 초과로 인해 2차원 배열 arr를 인접리스트로 변경

//before
...
	static int[][] arr;
	static int[] indegree;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		sc.nextLine();
		
		arr = new int[N+1][N+1];
		
		indegree = new int[N+1];
		
        for(int i=0; i<M; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            arr[from][to] = 1;
            indegree[to]++;
        }
		bfs();
	}
	
	public static void bfs(){
		Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        
        // 진입차수가 0인 노드를 큐에 추가
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current); // 처리된 정점을 결과 리스트에 추가
            
            for (int i = 1; i <= N; i++) {
                if (arr[current][i] == 1) {
                    indegree[i]--; // 해당 정점에서 나가는 간선을 제거
                    if (indegree[i] == 0) {
                        queue.add(i);
                    }
                }
            }
        }
        
        // 결과 출력
        for (int node : result) {
            System.out.print(node + " ");
        }
    }
}

//after
...
	 static List<Integer>[] List;
	
	static int[] indegree;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		//sc.nextLine(); -> 초기화도 삭제!!
		
		//arr = new int[N+1][N+1];
		List = new ArrayList[N+1];
		indegree = new int[N+1];
		
		
		for (int i = 1; i <= N; i++) {
			List[i] = new ArrayList<>();
		}

        for(int i=0; i<M; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            //arr[from][to] = 1;
            List[from].add(to);
            indegree[to]++;
        }
		bfs();
	}
	
	public static void bfs(){
		//Queue<Integer> queue = new LinkedList<>();
    //List<Integer> result = new ArrayList<>();
		PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 진입차수가 0인 노드를 큐에 추가
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                pq.add(i);
            }
        }
        
        while (!pq.isEmpty()) {
            int n = pq.poll();
            System.out.print(n + " ");
            
            for (int i : List[n]) {
                indegree[i]--; // 해당 정점에서 나가는 간선을 제거
                    
                if (indegree[i] == 0) {
                    pq.add(i);
                }
            }
        }
    }
}

최종 풀이

실제 풀이 시간 : 1시간 6분(첫 풀이 시간 포함)

입력
- 학생 수 N 입력받기
- 비교 횟수 M 입력받기
- 2차원 배열 arr 입력받기
계산
- bfs 계산하기
출력
- 결과 result 출력하기
별도 메서드
- BFS
  - 너비 우선 탐색 진행 → 큐 사용
    - 큐 선언
    - 큐 add
    - 방문하지 않은 노드를 true로 설정
    - 큐가 비어있지 않는 동안
      - 큐 poll
      - 현재 노드와 연결된 노드를 찾기
        
        해당 노드가 방문되지 않았다면 → 큐에 추가 + 방문으로 변경

import java.util.*;

public class Main {
	
	static int N;
	static int M;
	
	//static int[][] arr;
	 static List<Integer>[] List;
	
	static int[] indegree;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		//sc.nextLine();
		
		//arr = new int[N+1][N+1];
		List = new ArrayList[N+1];
		indegree = new int[N+1];
		
		
		for (int i = 1; i <= N; i++) {
			List[i] = new ArrayList<>();
		}

    for(int i=0; i<M; i++) {
        int from = sc.nextInt();
        int to = sc.nextInt();
        //arr[from][to] = 1;
        List[from].add(to);
        indegree[to]++;
    }
		bfs();
	}
	
	public static void bfs(){
		//Queue<Integer> queue = new LinkedList<>();
    //List<Integer> result = new ArrayList<>();
		PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 진입차수가 0인 노드를 큐에 추가
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                pq.add(i);
            }
        }
        
        while (!pq.isEmpty()) {
            int n = pq.poll();
            System.out.print(n + " ");
            
            for (int i : List[n]) {
                indegree[i]--; // 해당 정점에서 나가는 간선을 제거
                    
                if (indegree[i] == 0) {
                    pq.add(i);
                }
            }
        }
    }
}

이하얀

언젠가 내 코드로 세상에 기여할 수 있도록, BE&Data Science 개발 기록 노트☘️