[99클럽 코테 스터디 TIL#5일차] 백준 24444

문제

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

 

 

문제 풀기

 

1. 넓이 우선 탐색

무방향 그래프에서 넓이 우선 탐색 사용해 노드 방문 순서를 출력하는 문제였다.

 

2. 큐

넓이 우선 탐색 구현에 사용할 큐는 LikedList를 사용해서 구현했다.

 

3. 런타임 에러

NoSuchElement 에러가 발생했다. 실수로 List 범위 밖의 요소를 가져오려고 하는 코드를 작성했다.

 

 

 

 작성한 코드

import java.util.Queue;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;
public class Main{
    
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public static Queue<Integer> queue = new LinkedList<>();
    public static int[] visited;
    public static int cnt;
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int start = sc.nextInt();
        
        for(int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int i = 0; i < m; i++) {
            
            int u = sc.nextInt();
            int v = sc.nextInt();
            
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        for(int i = 1; i < n + 1; i++) {
            Collections.sort(graph.get(i));
        }
        
        visited = new int[n + 1];
        cnt = 1;
        visited[start] = cnt;
        
        bfs(start);
        
        for(int i = 1; i < n + 1; i++){
            System.out.println(visited[i]);    
        }
        
    }
    
    public static void bfs(int idx) {
        
        queue.add(idx);
        
        while(!queue.isEmpty()) {           
            int u = queue.poll();
            
            for(int i = 0; i < graph.get(u).size(); i++) {               
                if(visited[graph.get(u).get(i)] == 0) {                   
                    visited[graph.get(u).get(i)] = ++cnt;
                    queue.add(graph.get(u).get(i));             
                }
            }
        }
    
    }
}

 

 

 

개선할 점

 

Scanner vs BufferedReader

 

다른 분들의 코드를 보니 Scanner 대신 BufferedReader로 입력을 구현하시는 분이 많았다. Scanner가 다양한 데이터 타입을 바로 읽어오는 메서드가 있어서 간편하고 코드도 간결하게 쓰여진다는 점이 좋아서 사용하였는데, BufferedReader는 코드는 길어지지만 속도가 Scanner보다 빠르고 효율적이라는 점이 장점이었다.

 

코딩 테스트에선 많은 양이 입력 데이터를 다루는 문제도 있고 속도가 중요하니 코드가 길어져도 BufferedReader를 사용하려고 노력해야겠다.