[백준] 2750 숨바꼭질 4 - BFS(너비우선탐색) + 부모경로찾기(find Parent, LCA) JAVA

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

13913번: 숨바꼭질 4

코드설명

BFS(너비우선탐색) + 부모경로찾기(find Parent, LCA) 를 활용합니다.

 

1. BFS 메서드
   • BFS를 사용하여 최단 경로를 찾습니다.
   • 큐를 이용하여 탐색을 진행하고, 방문한 정점은 visited 배열을 통해 확인합니다.
   • 목표 정점인 K에 도달하면 최단 경로의 이동 횟수를 출력하고, 이동 경로를 스택을 활용하여 출력합니다.
   • 각 정점의 부모를  parent 배열에 저장하여 올라가면서 처리할 수 있도록 합니다.
2. 주요 로직:
   • 각 정점에서 이동 가능한 세 가지 경우를 고려합니다.
     • 이동 방향이 왼쪽(-1), 오른쪽(1)인 경우: 현재 위치에서 해당 방향으로 이동합니다.
     • 이동 방향이 순간이동(2)인 경우: 현재 위치에서 2배로 순간이동합니다.
   • 이동한 정점이 범위를 벗어나지 않고, 방문하지 않은 경우에만 이동합니다.
   • 방문한 정점은 visited 배열에 이동 횟수를 저장하고, 각 부모의 위치를 parent 배열에 저장합니다.

 

문제에서 유의해야했던 점은, visited배열에 이동횟수를 저장할때, parent 배열을 올바르게 사용하기 위해서는 이미 방문한곳은 다시 방문하지 않도록 처리합니다.

 

처음에는 아래와 같이 미리 방문한 곳보다 비교하여 더 빠르게 올경우 처리하였지만, 

Arrays.fill(visited, Integer.MAX_VALUE);
if(visited[nx] <= temp.cnt) continue; //한번 방문했던 곳보다 더 작은 숫자로 도착한경우가 있다면 중단

생각해보면, BFS에서 해당 경로를 더 빠르게 올 가능성이 없습니다.

그러므로 방문한 경험이 있다면 비교하지 않고, 방문한 경험이 있다면 더이상 탐색할 수 없게 처리하는것이 더 좋습니다.

 

코드

BFS 시간초과, 메모리초과 해결코드입니다.

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

public class Main {
	public static int N, K;
	public static int[] dx = {-1,1, 2};
	public static int[] visited = new int[100001];
	public static int[] parent = new int[100001];
    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());
    	K = Integer.parseInt(st.nextToken());
    	
    	BFS();
    }
    
    public static void BFS() {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(N, 0));
    	visited[N] = 0;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		
    		if(temp.x == K) {
    			System.out.println(temp.cnt);
    			
    			Stack<Integer> stack = new Stack<>();
    			int curPosition = K;
    	    	while(curPosition != N) {
    	    		stack.push(curPosition);
    	    		curPosition = parent[curPosition];
    	    	}
    	    	stack.push(N);
    	    	
    	    	while(!stack.isEmpty()) {
    	    		System.out.print(stack.pop() + " ");
    	    	}
    			
    			System.exit(0);
    			return ;
    		}
    		
    		for(int dir = 0; dir<3;dir++) {
    			int nx = temp.x + dx[dir];
    			if(dir == 2) {
    				nx = temp.x * 2;
    			}
    			if(nx < 0 || nx > 100000) continue;
    			if(visited[nx] > 0) continue;
    			parent[nx] = temp.x; 
    			visited[nx] = temp.cnt + 1;
    			q.offer(new Node(nx, temp.cnt + 1));
    		}
    		
    		
    		
    	}
    }
    
    
}

class Node{
	int x;
	int cnt;
	public Node(int x, int cnt) {
		this.x = x;
		this.cnt = cnt;
	}
}

 

BFS에서 STringbuilder를 사용했을떄 메모리초과 나는 코드.

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

public class Main {
	public static int N, K;
	public static int[] dx = {-1,1, 2};
	public static int[] visited = new int[100001];;
    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());
    	K = Integer.parseInt(st.nextToken());
    	
    	BFS();
    }
    
    public static void BFS() {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(N, 0, new StringBuilder().append(N).append(" ")));
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		
    		if(temp.x == K) {
    			System.out.println(temp.cnt);
    			System.out.println(temp.sb.toString());
    			return ;
    		}
    		
    		for(int dir = 0; dir<3;dir++) {
    			int nx = temp.x + dx[dir];
    			if(dir == 2) {
    				nx = temp.x * 2;
    			}
    			if(nx < 0 || nx > 100000) continue;
    			if(visited[nx] > temp.cnt) continue;
    			q.offer(new Node(nx, temp.cnt + 1, new StringBuilder(temp.sb.toString()).append(nx).append(" ")));
    		}
    	}
    }
    
    
}

class Node{
	int x;
	int cnt;
	StringBuilder sb = new StringBuilder();
	public Node(int x, int cnt, StringBuilder sb) {
		this.x = x;
		this.cnt = cnt;
		this.sb = sb;
	}
}

 

처음에 DFS로 풀어본 코드. 이렇게 할경우 최단거리를 찾지 못한다. 무조건 찾기 떄문입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int N, K;
	public static int[] dx = {-1,1};
    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());
    	K = Integer.parseInt(st.nextToken());
    	
    	DFS(0, N, new StringBuilder());
    }
    
    public static void DFS(int level, int curX, StringBuilder sb) {
    	if(curX == K) {
    		System.out.println(level);
    		sb.append(curX);
    		System.out.println(sb.toString());
    		System.exit(0);
    		return ;
    	}
    	DFS(level + 1, curX + 1, sb.append(curX).append(" "));
    	DFS(level + 1, curX - 1, sb.append(curX).append(" "));
    }
    
    
}