[백준] 22868 산책 (small) - BFS + 아이디어 + 시간초과 JAVA

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

22868번: 산책 (small)

문제풀이

BFS 문제에 Visited 배열만 사용하는것이 아닌,

S -> E로 갈때의 이력을 남기기 위해 visitedNodeCheck[] 을 활용하여야 했던 문제입니다.

이력을 남기는 이유는 E -> S로 갈떄 S -> E로 온 Node는 피해서 가기 위함입니다.

 

큰 코드틀을 말해보면,

1. BFS(S, E)

2. S -> E 로 가면서 방문햇던 노드들을 방문처리합니다. ( S 는 다시 방문해야하니 다시 방문처리를 해제합니다.)

3. BFS(E, S) 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N,M;
	public static ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
	public static int S, E;
	public static boolean[] visited;
	public static int[] visitedNodeCheck;
	public static int result = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	visited = new boolean[N+1];
    	visitedNodeCheck = new int[N+1];
    	for(int i=0;i<=N;i++) {
    		arr.add(new ArrayList<>());
    	}
    
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int nodeA = Integer.parseInt(st.nextToken());
    		int nodeB = Integer.parseInt(st.nextToken());
    		
    		arr.get(nodeA).add(nodeB);
    		arr.get(nodeB).add(nodeA);
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	S = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
 
    	// 문제조건 : S -> E 로 이동할시 사전순으로 가장 먼저 오는것을 선택합니다. 
        // 문제에 간선 무게가 모두 1 이기에 Integer로 받아서 COllections Sort를 합니다.
        // 만약 Node 객체 형식이라면 좀 더 Node 객체의 Comparable 을 구현하여서 사용하여야합니다.
    	for(int i=0;i<=N;i++) {
    		Collections.sort(arr.get(i));	
    	}
    	//BFS(시작, 종점)	
    	BFS(S, E);
        //모든 방문노드를 일단 초기화시킵니다.
    	Arrays.fill(visited, false);
    	
        //visitedNodecheck는 각 노드의 이전 노드를 저장하고 있습니다.
        //기본적으로는 0 일시 한번도 방문하지 않은 노드라는 뜻입니다.
        
        //E -> S로 갈때 S -> E로 갈떄 방문했던 곳은 방문하지 않기 위하여 
        //visited[] = true 처리를 합니다.
    	int lastNode = visitedNodeCheck[E];
    	while(lastNode > 0) { //S로 돌아갈시 visitedNodeCheck[lastNode]는 0입니다.(첫 초기화작업)
    		visited[lastNode] = true;
    		lastNode = visitedNodeCheck[lastNode]; //E에서 S로 돌아가는 과정을 돌면서 방문했던 노드들을 다시 방문처리하기 위함입니다.
    	}
    	visited[S] = false;
    	BFS(E, S);
    	System.out.println(result);
    }
    
    public static void BFS(int s, int e) {
    	Queue<Node> q = new LinkedList<>();
    	
    	q.offer(new Node(s, 0));
    	visited[s] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int index = temp.index;
    		int dist = temp.dist;
    		
    		for(int i=0;i<arr.get(index).size();i++) {
    			int nIndex = arr.get(index).get(i);
                //다음 노드가 이미 방문한적있다면 방문하지 않습니다.
    			if(visited[nIndex] == true) continue;
    			visited[nIndex] = true;
                //visitedNodeCheck에 방문노드의 index를 넣습니다.
    			visitedNodeCheck[nIndex] = index;
    			q.offer(new Node(nIndex, dist + 1));
    			//다음 Node가 목표 e 와 같다면 종료하고, 지금까지 dist 의 값을 더해주고 바로 종료시킵니다.
    			if( nIndex == e ) {
    				result += dist + 1;
    				return ;
    			}
    		}
    		
    	}
    }
    
    
}
 
class Node{
	int index;
	int dist;
	public Node(int index, int dist) {
		this.index = index;
		this.dist = dist;
	}
}