Koala - 5기/코딩테스트 준비 스터디

[BOJ / JAVA] 16930 - 달리기

김호식 3마리 치킨 2022. 2. 18. 13:48

문제

풀이

BFS 문제입니다. 어느 위치에서 움직일 수 있는 거리 k까지 field[][]에 count +1를 저장합니다.

추후에 이 값과 비교하여 더 작으면 skip(boolean visit[][]과 같은 동작) 하고,

아닐경우 값을 저장합니다.

field[x2] [y2] 의 값을 출력합니다.

코드

import java.io.*;
import java.util.*;

class Main {
	static int dx[] = {0,0,-1,1};
	static int dy[] = {-1,1,0,0};
	static int k;
	static int n;
	static int m;
	static int chk=1;
	static char field[][];
	static int field1[][];
	static boolean visit[][];
	static class now{
		private int x;
		private int y;
		private int num[] = new int [4];
		private int count = 0;
		
		now(int x, int y){
			this.x=x;
			this.y=y;
		}
		
		now(int x, int y, int count){
			this.x=x;
			this.y=y;
			this.count = count;
		}
		
	}
		
		
		static public void main(String[] args) throws IOException{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			Queue<now> q = new LinkedList<>();
			
			StringTokenizer st;
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			field = new char[n][m];
			field1 = new int [n][m];
			visit =new boolean [n][m];
			for(int i=0;i<n;i++) {
				Arrays.fill(field1[i],Integer.MAX_VALUE);
			}
			for(int i=0;i<n;i++) {
				String temp1 = br.readLine();
				for(int j=0;j<m;j++) {
					field[i][j] = temp1.charAt(j);
				}
			}
			
		st = new StringTokenizer(br.readLine());
		int x1 = Integer.parseInt(st.nextToken())-1;
		int y1 = Integer.parseInt(st.nextToken())-1;
		int x2 = Integer.parseInt(st.nextToken())-1;
		int y2 = Integer.parseInt(st.nextToken())-1;
		q.add(new now (x1, y1, 0));
		field1[x1][y1] = 1;
		while(!q.isEmpty()) {
			now temp = q.poll();
			for(int i=0;i<4;i++) {
				int tempx = temp.x;
				int tempy = temp.y;
				int num = 0;
				while(num<k) {
					tempx+=dx[i];
					tempy+=dy[i];
					num++;
					if(tempx<0 || tempx >= n) {
						break;}
					else
						if(tempy < 0 || tempy >= m) {
							
							break;
							}
						else
							if(visit[tempx][tempy])
								break;
							else
							if(field[tempx][tempy]=='#') {
								break;		
							}
							else {
					if(field1[tempx][tempy]<temp.count+1)
						break;
					if(field1[tempx][tempy]==Integer.MAX_VALUE) {
						field1[tempx][tempy] = temp.count+1;
						q.add(new now(tempx,tempy,temp.count+1));
					}
					}
				}
				if(field1[x2][y2]!=Integer.MAX_VALUE)
					break;
			}
		}
		if(field1[x2][y2]==Integer.MAX_VALUE)
			bw.write("-1");
		else
		bw.write(String.valueOf(field1[x2][y2]));
		
		bw.flush();
		
		}
	}

정답