백준[14940]번 : 쉬운 최단거리 ( JAVA )

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

14940번: 쉬운 최단거리

---

Code

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

public class Main {
	static Queue<int[]> queue = new LinkedList<>();
	
	static int[] ArrX = {1,-1,0,0}; // 상하좌우를 조절할 배열
	static int[] ArrY = {0,0,1,-1};
	static int n,m;
	static int[][] map; //입력을 저장할 배열
	static int[][] ans;// 답을 저장할 배열
	static boolean[][] 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());
		
		map = new int[n][m];
		ans = new int[n][m];
		visit = new boolean[n][m];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			
			for(int j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				if(map[i][j] == 2) { // 2가 있는 곳 부터 queue에 넣고 시작
					queue.add(new int[] {i,j});
					visit[i][j] = true;
					ans[i][j] = 0;
				}
				if(map[i][j] == 1) { // 길이 막힌 경우 -1을 출력해야 하기에 정답에 -1을 넣고 시작
					ans[i][j] = -1;
				}
			}
		}
		
		/* 
		3 3
		2 0 0
		0 0 1
		0 1 1
		*/
		bfs();
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				bw.write(ans[i][j]+" ");
			}
			bw.write("\n");
		}
		
		br.close();
		bw.close();
	}
	
	static void bfs() {
		while(!queue.isEmpty()) {
			int[] arr = queue.poll();
			
			int y = arr[0];
			int x = arr[1];
			
			for(int i=0;i<4;i++) { // 상하좌우 하나씩 검사
				int ny = y + ArrY[i];
				int nx = x + ArrX[i];
				
				if(ny < 0 || ny >= n || nx < 0 || nx >= m) { //패스
					continue;
				}
				
				if(visit[ny][nx]) {//패스
					continue;
				}
				
				visit[ny][nx] = true; // 방문기록
				
				if(map[ny][nx] == 0) { 
					ans[ny][nx] = 0;
					continue;
				}
				
				ans[ny][nx] = ans[y][x] + 1; // 이전 자리에서 1칸만 움직이면 되므로 1추가
				
				queue.add(new int[] {ny,nx});
			}
		}
	}
}

---

처음 2의 위치를 받아 queue에 넣는 것으로 시작한다.

2의 위치에 0을 넣고 거리 1을 더해준다.

그 후 queue에 넣어 계속해서 거리를 1씩 늘려주는 방식이다.

 

문제를 제대로 읽지 않아 -1을 출력한다는 조건을 못 보고 풀었다.

이 부분에서 시간을 많이 썼는데 생각지 못한 쉬운 방법이 있었다.

 

처음 map에 1이 들어왔을 때 ans의 해당 위치에 -1로 저장해 주면 된다.