[HackerRank]Breadth First Search: Shortest Reach

https://www.hackerrank.com/challenges/bfsshortreach/problem
하... 이 글 진짜 쓰고 싶었다.
왜냐하면 너무 어려웠기 때문이다.

우선 BFS 문제를 백준에서 푼 적이 있었고 단순하게 방문 노드만 체크하면 된다고 생각했다.
하지만 여기서의 포인트는 BFS의 level을 따지는 것이었다.

백준에서 풀었던 과거 코드까지 되돌아보게 된 계기가 되었다.

우선 나의 원래 코드는 아래와 같다

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

public class Main{
	static Queue<Integer> bq = new LinkedList<>();
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void print_bq(Queue<Integer> bq) throws Exception{
		while(!bq.isEmpty()) {
			bw.write(bq.poll() + " ");
		}
		bw.write("\n");
	}
	
	public static void bfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, Queue<Integer> q, int N, int M) {
		//종료조건
		if(N <= M) {
			if(bq.size() == N) return ;
		} else {
			if(bq.size() == M+1) return ;
		}
		
		int front = q.peek();
		//예외처리 : 시작점이 간선이 없는 정점일 때 
		if(adj.get(front).size() == 0) {
            bq.add(front);
			return ;
		}
		
		if(visited[front] != true) {
			q.poll();
			bq.add(front);
			visited[front] = true;
			
			for(int i=0;i<adj.get(front).size();i++) {
				if(visited[adj.get(front).get(i)] != true) {
					q.add(adj.get(front).get(i));
				}
			}
		} 
		else {
			q.poll();
		}
		
		bfs(adj, visited, q, N, M);
	}
	

	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		boolean[] visited = new boolean[N+1];
		Queue<Integer> q = new LinkedList<>();
		
		//인접리스트
		ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
		//인접리스트 생성
		for(int i=0;i<=N;i++) {
			adj.add(new ArrayList<Integer>());
		}
		//인접리스트 구현
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int val1 = Integer.parseInt(st.nextToken());
			int val2 = Integer.parseInt(st.nextToken());
			adj.get(val1).add(val2);
			adj.get(val2).add(val1);
		}
		
		
		//인접리스트 정렬
		for(int i=0;i<=N;i++) {
			Collections.sort(adj.get(i));
		}
	
		//call bfs
		q.add(V);
		bfs(adj, visited, q, N, M);
		print_bq(bq);
		
		br.close();
		bw.flush();
		bw.close();
	}
}

이 코드에서 레벨을 구해주면 된다고 생각했지만, 나의 코드 자체가 레벨을 구하기에 상당히 지저분한 코드였다ㅋ..

그래서 결국은 q에 추가된 크기만큼 레벨을 구해주면 된다는 아이디어엔 접근했지만 내 코드를 수정하는 걸론 불가능했다.
구글링 결과 매우 심플한 bfs 코드를 봤고 정말 배우는 시간이었다.

열심히 알고리즘 공부해야겠다. 정말 공부된다.

뿌 듯