[백준] 10709. 기상캐스터
JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다.
각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다.
지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다.
각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구하여라.
입력
입력은 1 + H 행으로 주어진다.
첫 번째 행에는 정수 H, W (1 ≦ H ≦ 100, 1 ≦ W ≦ 100) 가 공백을 사이에 주고 주어진다. 이것은 JOI시가 H × W 개의 작은 구역으로 나뉘어 있다는 것을 의미한다.
이어진 H 개의 행의 i번째 행 (1 ≦ i ≦ H) 에는 W문자의 문자열이 주어진다. W 개의 문자 중 j번째 문자 (1 ≦ j ≦ W) 는, 구역 (i, j) 에 지금 구름이 떠 있는지 아닌지를 나타낸다. 구름이 있는 경우에는 영어 소문자 'c' 가, 구름이 없는 경우에는 문자 '.' 가 주어진다.
출력
출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시한다. 단, 처음부터 구역 (i, j) 에 구름이 떠 있었던 경우에는 0을, 몇 분이 지나도 구름이 뜨지 않을 경우에는 -1을 출력한다.
예제 입력 2
6 8
.c......
........
.ccc..c.
....c...
..c.cc..
....c...예제 출력 2
-1 0 1 2 3 4 5 6
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 1 2 0 1
-1 -1 -1 -1 0 1 2 3
-1 -1 0 1 0 0 1 2
-1 -1 -1 -1 0 1 2 3import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static int H, W;
public static int[][] arr;
public static Queue<Point> queue;
public static class Point {
int h;
int w;
int cnt;
public Point(int h, int w, int cnt) {
this.h = h;
this.w = w;
this.cnt = cnt;
}
}
public static void main(String[] args) throws Exception {
StringTokenizer st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
queue = new LinkedList<>();
arr = new int[H][W];
for(int i = 0; i < H; i++) {
char[] ch = br.readLine().toCharArray();
for(int j = 0; j < W; j++) {
if(ch[j] == 'c') {
queue.add(new Point(i, j, 0));
arr[i][j] = 0;
} else {
arr[i][j] = -1;
}
}
}
while(!queue.isEmpty()) {
Point current = queue.poll();
arr[current.h][current.w] = current.cnt;
int nw = current.w + 1;
if(nw < W && arr[current.h][nw] == -1) {
queue.add(new Point(current.h, nw, current.cnt + 1));
}
}
for(int[] i : arr) {
for(int j : i) {
bw.write(j + " ");
}
bw.newLine();
}
br.close();
bw.flush();
bw.close();
}
}현재 구름의 위치를 전부 찾아 큐에 담는다.
그리고 .을 입력받은 부분은 전부 -1로 초기화해준다. 최종 출력 시 재검사를 안하고 구름이 뜨지않는 구간을 -1로 출력하기 때문이다.
큐에 들어있는 현재값을 꺼내 현재 배열에 cnt값(분)을 저장하고 오른쪽으로 한칸 이동시켜 준 후 해당 위치가 빈 땅이면(-1) 큐에 새로운 위치를 넣고 count를 하나 늘려준다
큐가 전부 다 돌면 현재 배열은 전부 cnt값을 저장하고 있고 빈 땅인부분은 -1이 저장되어 있다.