문제 정리

---

Joi시의 각 지역에 구름이 뜨는 최초의 시간을 계산한다
마을은 H x W 크기이고 각 지역은 1 x 1 크기이다
구름은 동쪽(오른쪽)으로만 움직인다

입력

H W
지역의 정보

c : 구름이 뜬 자리
. : 구름이 뜨지 않은 자리

출력

구름이 뜨는 시간 정보가 포함된 지역 정보

0 : 처음 구름이 뜬 지역
-1 : 구름이 끝까지 지나가지 않은 지역
구름이 처음 발견되는 시각

idea 정리

---

문제를 어떻게 풀까 하다가 bfs가 떠올랐다
구름의 정보를 q에 넣고 하나씩 꺼내면서 이동한걸 다시 저장한다
모든 구름이 이동하는것이 한 레벨 탐색이라고 생각하면 된다

bfs에서는 더이상 연결된 곳이 없으면 멈추는데
이 문제에서는 구름이 맵 범위를 벗어나거나 이미 구름이 지나간 지역을 만나게 되면
연결된 곳이 없다고 판단하는거다

정리하자면

정점과 연결된 지점 -> 현재 구름의 바로 오른쪽의 지역
너비 탐색 -> 모든 구름이 오른쪽으로 한 칸씩 움직임
이다

알고리즘 구성

---

1. 배열을 입력받을 때 구름의 정보를 queue에 저장
2. queue에 저장된 모든 구름을 오른쪽으로 이동
3. 만약 이동하려는 지역이
   이미 구름이 지나갔거나 최초에 구름이 있었던 자리면 구름이 소멸한다고 판단
4. 구름이 이동하면 시간 정보를 배열에 업데이트
5. queue에 원소가 없을 때 까지 2~4 반복

구현

---

//기상캐스터
public class Main {
	
	static class Cloud{
		int r,c;

		public Cloud(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	static int H,W;
	static int[][] map;
	static boolean[][] clouded;      //구름이 지나간 자리 표시
	static Queue<Cloud> clouds;
	
	static int dc = 1;   // 행은 안움직이고 열만 오른쪽으로 움직임
	
	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(), " ");
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		
		map = new int[H][W];
		clouded = new boolean[H][W];
		clouds = new LinkedList<>();
		
		for(int i=0; i<H; i++) {
			char[] input = br.readLine().toCharArray();
			
			for(int j=0; j<W; j++) {
				if(input[j]=='c') {
					map[i][j] = 0;
					clouded[i][j] = true;
					clouds.add(new Cloud(i, j));
				}
				else map[i][j] = -1;
			}
		}
		
		int time=0;
		while(!clouds.isEmpty()) {
			time++;                             //모든 구름의 이동 연산이 끝나는 것이 한 레벨 탐색
			for(int i=0, size=clouds.size(); i<size; i++) {
				Cloud now = clouds.poll();
				
				int nr = now.r;
				int nc = now.c + dc;
				if(nc >= W || clouded[nr][nc] || map[nr][nc]>=0) continue;  //배열의 범위를 벗어나거나 이미 구름이 지나간 경우
				clouded[now.r][now.c] = false;
				clouded[nr][nc] = true;
				map[nr][nc] = time;
				clouds.add(new Cloud(nr, nc));    //아직 오른쪽으로 이동할 수 있으니 다시 q에 넣어줌
			}
		}
		
		
		for(int i=0; i<H; i++) {
			for(int j=0; j<W; j++) {
				bw.write(map[i][j] + " ");
			}
			bw.write("\n");
		}
		bw.flush();
		bw.close();
		br.close();
		
	}
}

결과

---