HackerRank BFS: Shortest Reach in a Graph

Problem Link : https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem

1. Thinking & Feedback

• 최단거리를 구하는 문제이기에 BFS 를 생각
• Brute Force 로 푼 뒤 최적화를 생각
• Start 지점 에서 노드 간 거리를 저장하는 방법에 대해서 고민
  • 인접 edgeNum 을 조회하면서 배열로 저장해 값이 없는건 -1 로 출력하기로 함.
• while 문을 돌면서 Length 6씩 증가하는 방법을 사용하니 같은 레벨의 Distance 가 가중되면서 나오는 오류
  • 이 문제는 이전 노드의 res[nodeNum] + 6 으로 해결. 왜냐하면 인접노드는 결국 서로 붙어있기에 이전노드 + 6 을 하면 같이 나옴.

2. Source

public class ShortestReachInAGroup
{	
	private static Map> graph; 
	private static boolean visited[];
	
	private static int n;
	
	public static void main(String [] args)
	{
		Scanner in = new Scanner(System.in);
	
		// number of queries
		int q = in.nextInt();
		
		for (int j = 0 ; j < q ; j++)
		{
			// number of node
			n = in.nextInt();
			
			graph = new HashMap>();
			visited = new boolean[n + 1];
			
			for (int k = 1 ; k <= n ; k++)
			{
				graph.put(k, new ArrayList());
			}
			
			// number of edges
			int m = in.nextInt();
			
			for (int i = 0 ; i < m ; i++)
			{
				int u = in.nextInt(); 
				int v = in.nextInt();
				
				graph.get(u).add(v); 
				graph.get(v).add(u);
			}
			
			int s = in.nextInt();
			
			int res[] = BFS(s);
			
			printAnswer(s, res);
		}
	}
	
	public static void printAnswer(int start, int res[])
	{
		for (int i = 1 ; i < res.length ; i++)
		{
			if (start == i)
				continue;
			
			if (res[i] == 0)
				System.out.print(-1 + " ");
			else
				System.out.print(res[i] + " ");
		}
		System.out.println();
	}
	
	public static int[] BFS(int start)
	{
		Queue queue = new LinkedList();
		queue.add(start);
		
		int res[] = new int[n + 1];
		int nodeNum = 0;
		
		visited[start] = true;
		
		while ( !queue.isEmpty())
		{
			nodeNum = queue.poll();
			for (Integer edgeNum  : graph.get(nodeNum))
			{
				if (visited[edgeNum] == false)
				{
					queue.add(edgeNum);
					res[edgeNum] = res[nodeNum] + 6;
					visited[edgeNum] = true;
				}
			}
		}
		return res;
	}
}