11725 자바

ArrayList로 이중배열 만들기

-> ArrayList의 원소로서 다시 ArrayList을 사용하는 방식

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		for (int i = 0; i < n; i++)
			graph.add(new ArrayList<>());

for(int i=1;i<N+1;i++){
    int a=sc.nextInt();
    int b=sc.nextInt();
    graph.get(a).add(b);
    graph.get(b).add(a);
}

우변은 <>로 써서 타입 유추할 수 있게 함. 좌변처럼 쓰기엔 너무 길어서 귀찮으므로

형태: graph라는 ArrayList 안에 여러 개의 ArrayList 타입의 객체들이 있다.

---

 

BFS를 구현하기 위해 덱을 사용할 것이다.

자바에서는 덱을 4가지 방법으로 구현할 수 있다

Deque<String> deque1 = new ArrayDeque<>();
Deque<String> deque2 = new LinkedBlockingDeque<>();
Deque<String> deque3 = new ConcurrentLinkedDeque<>();
Deque<String> linkedList = new LinkedList<>();

 

사용가능한 메소드

deque.addFirst(); // Deque의 앞쪽에 데이터를 삽입, 용량 초과시 Exception
deque.offerFirst(); //  Deque의 앞쪽에 데이터를 삽입 후 true, 용량 초과시 false

deque.addLast(); // Deque의 뒤쪽에 데이터를 삽입, 용량 초과시 Exception
deque.add(); // addLast()와 동일
deque.offerLast(); //Deque의 뒤쪽에 데이터를 삽입 후 true, 용량 초과시 false
deque.offer(); // offerLast()와 동일

deque.push(); // addFirst()와 동일
deque.pop(); // removeFirst()와 동일

 

deq 값 확인하는 메소드

deque.getFirst(); // 첫 번째 엘리먼트를 확인, 비어있으면 예외
deque.peekFirst(); // 첫 번째 엘리먼트를 확인, 비어있으면 null 리턴
deque.peek();// peekFirst()와 동일

deque.getLast(); // 마지막 엘리먼트를 확인, 비어있으면 예외
deque.peekLast();// 마지막 엘리먼트를 확인, 비어있으면 null 리턴

deque.contain(Object o); // Object 인자와 동일한 엘리먼트가 포함되어 있는지 확인
deque.size(); // Deque에 들어있는 엘리먼트의 개수

---

객체 생성만하고 초기화 안한 경우

ex) boolean[] visited = new boolean[N+1];

-> if(!visited[i]) 라고 작성함으로써 원소 저장 안된 상태인지 확인 가능

---

최종코드

import java.util.*;



public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N=sc.nextInt();
        ArrayList<ArrayList<Integer>> graph= new ArrayList<>();
        for (int i=0;i<=N+1;i++){
            graph.add(new ArrayList<>());  //초기화
        }
        boolean[] visited=new boolean[N+1];


        int[] parent = new int[N+1];

        for(int i=1;i<N;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        Deque<Integer> deq=new LinkedList<>();
        deq.addFirst(1);
        visited[1]= true;
        while(!deq.isEmpty()) {
            int c = deq.remove();
            for (int i = 0; i < graph.get(c).size(); i++) {
                int tmp = graph.get(c).get(i);
                if (!visited[tmp]) {
                    deq.addLast(tmp);
                    visited[tmp] = true;
                    parent[tmp] = c;
                }
            }
        }

        for(int i=2;i<N+1;i++){
            System.out.println(parent[i]);

        }




    }
}

 

 

Scanner대신 BufferedReader,StringTokenizer를 사용

 

import java.io.*;
import java.util.*;


public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Integer>> graph= new ArrayList<>();
        for (int i=0;i<=N+1;i++){
            graph.add(new ArrayList<>());  //초기화
        }
        boolean[] visited=new boolean[N+1];


        int[] parent = new int[N+1];
        StringTokenizer st;

        for(int i=1;i<N;i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        Deque<Integer> deq=new LinkedList<>();
        deq.addFirst(1);
        visited[1]= true;
        while(!deq.isEmpty()) {
            int c = deq.remove();
            for (int i = 0; i < graph.get(c).size(); i++) {
                int tmp = graph.get(c).get(i);
                if (!visited[tmp]) {
                    deq.addLast(tmp);
                    visited[tmp] = true;
                    parent[tmp] = c;
                }
            }
        }

        for(int i=2;i<N+1;i++){
            System.out.println(parent[i]);

        }




    }
}

근데 아래방법이 시간이랑 메모리를 조금 더 잡아 먹었다