BOJ - 16930 ) 달리기

---

 

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

16930번: 달리기

---

NXM맵에서 직선방향으로 K만큼 이동할때에, 목적지까지 갈수있는 최단 시간을 구하는문제이다.

 

최단시간이고 N,M이 1000이라 BFS로 풀릴것같았다.

 

먼저, K만큼

 

1 ) 이동중 범위를 벗어나는경우

2 ) # 벽을 만나는경우

 

이 두가지의 경우에는 K를 break처리해주었다.

 

---

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int sx=0,sy=0,ex=0,ey=0;
		char map[][] = new char[n+1][m+1];
		int visit[][] =new int[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);
				visit[i][j] = 987654321;
			}
		}
		st = new StringTokenizer(br.readLine());
		sy = Integer.parseInt(st.nextToken());
		sx = Integer.parseInt(st.nextToken());
		ey = Integer.parseInt(st.nextToken());
		ex = Integer.parseInt(st.nextToken()); //end input
		int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
		ArrayDeque<int []> dq = new ArrayDeque<>();
		dq.add(new int[] {sy,sx,1});
		visit[sy][sx] =0;
		while(!dq.isEmpty()) {
			int now[] =dq.poll();
			int nowy = now[0];
			int nowx = now[1];
			int time = now[2];
			
			if(nowy == ey && nowx == ex) {
				break;
			}
			for(int i = 0 ; i < 4 ; i++) {
				// 한방향을 정해서,
				for(int j = 1 ; j <=k ;j++) {
					int ny = nowy + dir[i][0]*j;
					int nx = nowx + dir[i][1]*j; // 갈수있는 최대 k까지
					if(ny > 0 &&nx >0 && nx <= m &&ny <=n) {
						if(map[ny][nx]=='.') {
							if(visit[ny][nx] > time) {
								// .이고 더 작은 시간으로 갈수있을때만 이동
								visit[ny][nx] = time;
								dq.add(new int[] {ny,nx,time+1});
							}
						} else {
							break;// 벽에 막힌경우
						}
					}
				}
			}
		}System.out.println(visit[ey][ex] = visit[ey][ex] == 987654321 ? -1 : visit[ey][ex]);
		
				
	}

}

---

결과는 90%에서 시간초과가 났다.

 

또 다른경우가 존재한다.. ( 한참고민 )

 

한 시간 내에 k만큼 이동할때에 Queue에는 1-k까지의 좌표들이 들어있게되는데, 사실상 모두 같은 시간을 가짐에도,

 

Queue에서 나왔을때에 같은 방향으로 k만큼 또 계산하게된다..

 

. . . .

. . . .

. . . .

. . . .

 

이러한 맵에서 시간1초후 Visit 배열은

 

1 1 1 1

1  .  .  .

1  .  .  .

1  .  .  .

 

가 될텐데, (1,2)의 노드에서 다시 하나를뽑아도 (1,3) (1,4) 쪽으로 for문이 돌게된다.

 

즉, 방문하지않았고, 방문했다면 더 적은시간이 체크된쪽을 방문할때에는 멈추어 주어야한다. 

 

위와같은상황에서 (1,3) , (1,4)쪽으로 진행되는 방향은 다시볼 필요가 없기 때문이다.

 

즉 visit[ny][nx] <= visit[nowy][nowx] 처럼 내가 가려고하는쪽이 같거나 더작은 시간을 가지고있다면,

 

볼필요가 없게되는 것이다.

 

---

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int sx=0,sy=0,ex=0,ey=0;
		char map[][] = new char[n+1][m+1];
		int visit[][] =new int[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());
		sy = Integer.parseInt(st.nextToken());
		sx = Integer.parseInt(st.nextToken());
		ey = Integer.parseInt(st.nextToken());
		ex = Integer.parseInt(st.nextToken()); //end input
		int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
		ArrayDeque<int []> dq = new ArrayDeque<>();
		dq.add(new int[] {sy,sx});
		visit[sy][sx] =0;
		top :
		while(!dq.isEmpty()) {
			int now[] =dq.poll();
			int nowy = now[0];
			int nowx = now[1];
			for(int i = 0 ; i < 4 ; i++) {
				// 한방향을 정해서,
				for(int j = 1 ; j <=k ;j++) {
					int ny = nowy + dir[i][0]*j;
					int nx = nowx + dir[i][1]*j; // 갈수있는 최대 k까지
					if(ny > 0 &&nx >0 && nx <= m &&ny <=n && map[ny][nx]=='.') {
						if(visit[ny][nx]==0) {
							// .이고 더 작은 시간으로 갈수있을때만 이동
							visit[ny][nx] =  visit[nowy][nowx]+1;
							if(ny == ey && nx == ex) {break top;}
							dq.add(new int[] {ny,nx});
						} else if(visit[ny][nx] <= visit[nowy][nowx]) {
                           // 더작은시간이 이미 계산되어있는 곳이라면 stop
							break;
						}
					} else {
						break;
					}
				}
			}
		}System.out.println(visit[ey][ex] = visit[ey][ex] == 0 ? -1 : visit[ey][ex]);
		
				
	}

}

 

---

간단한 BFS이지만 Queue에 삽입전에 조건만 조금 생각해준다면 시간복잡도를 크게 줄일수 있다 ( O(NMK) -> O(NM) )