mingssssss

1. 문제

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

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    
    // 전역 변수 설정
	static ArrayList<ArrayList<Integer>> list;
	static boolean[] visited;
	static int cnt;
	static ArrayList<Integer> answer;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());

		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		ArrayList<Integer> answer = new ArrayList<>();
		visited = new boolean[N + 1];

		for (int i = 0; i < N + 1; i++) {
			list.add(new ArrayList<Integer>()); // <Integer> 생략해도 되는지 확인
		}
		// list 입력 종료

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());

			list.get(Integer.parseInt(st.nextToken())).add(Integer.parseInt(st.nextToken()));
		}
		// 인접 리스트 입력 종료

		bfs(X, K, N, M, list, answer, visited);
        
        // answer의 size가 0 이라는 뜻은 거리가 K인 노드가 없는 경우
		if (answer.size() == 0) {
			System.out.println(-1);
		} else {
        	Collenctions.sort(answer); // 오름 차순으로 정렬
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < answer.size(); i++) {
				sb.append(answer.get(i) + "\n");
			}
			System.out.println(sb);
		}
	}

	public static void bfs(int X, int K, int N, int M, ArrayList<ArrayList<Integer>> list, ArrayList<Integer> answer, boolean[] visited) {

		Queue<Integer> q = new LinkedList<>();

		q.add(X); // 시작 좌표 입력

		cnt = 0;
		while (!q.isEmpty()) {
            
            // 거리를 체크하기 위해 size만큼 for문을 돌림
			int size = q.size();

			for (int i = 0; i < size; i++) {

				int v = q.poll();
				visited[v] = true;
				
                // 거리가 K와 같은 경우
				if (cnt == K) {
					answer.add(v);
				}
                
                // list를 순회
				for (int next : list.get(v)) {

					if (visited[next] == false) {

						visited[next] = true;
						q.add(next);
					}

				}
			}
            // 거리 1만큼 증가
			cnt++;
		}

	}

}
// 하영아 사랑해

3. 리뷰

로직과 구현 모두 무난한 문제였다. 하지만 실패가 떠서 문제를 다시 읽어보니 오름차순 정렬을 고려하지 않았다.

입력값이 제법 커서 처음부터 ArrayList로 입력 받고 StringBuilder로 출력했다.

채점 현황을 보니 다들 시간과 메모리에서 고생하는 것이 보였다.

문제는 단방향 노드가 주어지고, 시작점부터 도착점까지 주어진 거리만큼을 만족하는 노드를

오름차순으로 출력하는 문제이다.

방향을 ArrayList에 입력하고 시작지점부터 bfs를 순회해서 거리가 K와 같으면 answer 리스트에 추가했다.

이후 sort를 통해 오름차순으로 정렬하고 StringBuilder로 입력받아 출력했다.

저번에 배운 q의 size만큼만 돌아서 한 차수가 진행되면 cnt++를 해줬다.

배운 것을 유용하게 써먹을 수 있어서 뿌듯했다.