[백준] 16930 달리기 - JAVA

16930번: 달리기 (acmicpc.net)

16930번: 달리기

 

 

풀이

알고리즘 파악

 

BFS

 

한 번 이동할 때마다 K 만큼의 이동을 할 수 있다. 즉 진영이의 위치를 queue에 저장하고 동서남북 방향으로 최대 +k만큼의 범위를 저장하면 되는 것이다. 하지만 K가 최대 1000이기 때문에 모든 위치에서 매번 K*4 만큼 탐색을 하는 것은 매우 비효율적이다. 이 탐색 횟수를 줄이는 것이 이 문제의 핵심이다. 

 

구현 

 

1 탐색 위치가 인덱스 범위를 벗어나거나 벽과 만나면 탐색을 중단한다.

 

2 탐색 위치의 방문 시간이 더 작다면 탐색을 중단시킨다.

-> 문제의 포인트다. 예시를 들어보면

 

2 -> 새 방문 시간(현 방문 시간 +1)

1 -> 이전의 방문 시간 (아직 탐색을 시작 하지 않음)

0 -> 방문 하지 않음

밑줄 -> 현재 방문 위치

 

(오른쪽으로 k만큼 탐색 중인 경우)

 

1) 1 0 0 0

   현재 방문 위치의 시간이 0이다. 즉 방문하지 않았기에 새 방문 시간(현 방문 시간 +1)을 기록한다.    

 

 

2)  2 1 1 1 1 .....

    새 방문 시간 2 보다 1이 더 작다. 즉 이전 턴에 먼저 방문을 한 것이고, 오른쪽은 이미 탐색했으므로 추가적으로 탐색하는 것은 시간 낭비이니 BREAK 한다.  

      

 

      2

      2

3) 2 2 0 0 0.....

    내가 헷갈렸던 포인트이다. 처음에는 단순히 미리 방문한 곳을 방문하면 BREAK를 했는데 잘못된 생각이었다. 예시처럼 미리 방문한 곳이 있지만 새 방문 시간과 같을수가 있다. 즉 같은턴에 이미 방문을 했지만, 위에서 온것인지 아래에서 온것인지 확인 할 수 없다. 예시 처럼 오른쪽은 아직 방문을 한 적이 없지만 방문을 했다고 생각해 추가적인 탐색을 중지할 수 있다.  

 

 

import java.io.*;
import java.util.StringTokenizer;
import java.util.PriorityQueue;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int n,m,k;
	static int answer = 0;
	static char[][] map;
	static int[] end = new int[2];
	static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
	static Queue<int[]> q = new LinkedList<>();
	static int[][] visit;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
        StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); 
		m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        map = new char[n+1][m+1];
        for(int i=1; i<=n; i++)
        {
        	String str = br.readLine();
        	for(int j=1; j<=m; j++) map[i][j] = str.charAt(j-1);  
        }
        
        st = new StringTokenizer(br.readLine());
        
        int a = Integer.parseInt(st.nextToken()), b =Integer.parseInt(st.nextToken());
        int[] begin = {a,b};
        int c = Integer.parseInt(st.nextToken()), d =Integer.parseInt(st.nextToken());
        end[0] = c; end[1] = d;
        q.offer(begin);
        
        bfs();
        
		bw.write(Integer.toString(visit[end[0]][end[1]]));
        bw.flush();
        bw.close();
        br.close();
	}
	
	static void bfs()
	{
		visit = new int[n+1][m+1];

		while(!q.isEmpty())
		{
		    int[] arr = q.poll();
		    int x = arr[0], y= arr[1];
		 
		    for(int i=0; i<4; i++)
		    {
		    	for(int j=1; j<=k; j++)
		    	{
		    		int newX = x+(j*dx[i]), newY = y+(j*dy[i]);	
		    		if(newX>0 && newX<=n && newY>0 && newY<=m && map[newX][newY] == '.') 
		    		{
		    		   if(visit[newX][newY]==0)
		    	       {
		    			  visit[newX][newY] = visit[x][y]+1;   
		    	          if(newX ==end[0] && newY ==end[1]) return;	
		    		    
		    	          int[] temp = {newX,newY};
		    		      q.offer(temp);
		    	       }
		    		   else if(visit[newX][newY] == visit[x][y]) break;
		    		}
		    		else break;
		    	}
		    }
		}
		visit[end[0]][end[1]] = -1;
	}
}