https://www.acmicpc.net/problem/14940
목표지점에서 BFS를 진행하고 거리를 1씩 더하면서 진행하면 풀 수 있다.
입력으로 주어진 이차원 배열을 이용할 것이기 때문에 거리를 -1부터 시작한다.
public static void bfs(int trr, int tcc) {
Queue<int[]> queue = new LinkedList<>();
//초기화
queue.add(new int[]{trr, tcc, -1});
visit[trr][tcc] = true;
while (!queue.isEmpty()) {
int[] poll = queue.poll();
int r = poll[0];
int c = poll[1];
int cnt = poll[2];
map[r][c] += cnt;
for (int i = 0; i < 4; i++) {
int nr = r + dir[i][0];
int nc = c + dir[i][1];
if(nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
if(map[nr][nc] == 0) continue;
if(visit[nr][nc]) continue;
visit[nr][nc] = true;
queue.add(new int[]{nr, nc, cnt+1});
}
}
}
bfs에 사용하기 위한 Queue에 목표지점(시작지점)의 좌표를 넣고 거리 -1를 넣는다.
queue가 빌 때까지 (갈 수 있는 좌표가 없을 때 까지) 탐색을 진행한다.
좌표에서 위 아래 오른쪽 왼쪽을 이동할 수 있으므로 for문을 통해 갈 수 있는 좌표를 전부 queue에 넣는다.
package baekjoon._14940;
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 {
static int n, m;
static int[][] map;
static boolean[][] visit;
static int tr, tc;
static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
//입력
public static void input() {
FastReader fr = new FastReader();
n = fr.nextInt();
m = fr.nextInt();
map = new int[n][m];
visit = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = fr.nextInt();
//목표지점(시작지점)을 저장
if(map[i][j] == 2){
tr = i;
tc = j;
}
}
}
map[tr][tc]=1;
bfs(tr, tc);
}
public static void bfs(int trr, int tcc) {
Queue<int[]> queue = new LinkedList<>();
//초기화
queue.add(new int[]{trr, tcc, -1});
visit[trr][tcc] = true;
while (!queue.isEmpty()) {
int[] poll = queue.poll();
int r = poll[0];
int c = poll[1];
int cnt = poll[2];
map[r][c] += cnt;
for (int i = 0; i < 4; i++) {
int nr = r + dir[i][0];
int nc = c + dir[i][1];
if(nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
if(map[nr][nc] == 0) continue;
if(visit[nr][nc]) continue;
visit[nr][nc] = true;
queue.add(new int[]{nr, nc, cnt+1});
}
}
}
public static void print() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(!visit[i][j] && map[i][j]==1) sb.append(-1);
else sb.append(map[i][j]);
sb.append(" ");
}
sb.append('\n');
}
System.out.println(sb);
}
public static void main(String[] args) {
input();
print();
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}
String next(){
while(st == null || !st.hasMoreTokens()){
try{
st = new StringTokenizer(br.readLine());
} catch (IOException e){
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
Double nextDouble() { return Double.parseDouble(next()); }
String nextLine(){
String str = "";
try{
str = br.readLine();
} catch(IOException e){
e.printStackTrace();
}
return str;
}
}
}
목표지점까지의 거리를 구하는 문제이기 때문에 단번에 BFS를 떠올렸다.