백준 10709 기상캐스터

작성일 | In |

Problem : 기상캐스터

유형 : 구현

문제 설명

JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로와 세로의 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다.

각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다.

지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다.

각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구하여라.

예제 입력

1
2
3
4
3 4
c..c
..c.
....

예제 출력

1
2
3
0 1 2 0
-1 -1 0 1
-1 -1 -1 -1

해결 전략

구름을 움직이되, 범위를 벗어나거나 이미 구름이 지나간 곳이면 가지 않는다.

주의할 점

  • 없음

풀이

초기 구름의 위치를 찾는다.

처음에 모든 구역을 -1로 표시한다.
초기 구름이 있는 위치를 0으로 표시하고, 해당 위치를 큐에 넣는다. (굳이 큐가 아니어도 된다)

구름을 움직이는 함수

구름을 한칸씩 움직이는데, 범위 밖을 벗어나거나 이미 다른 구름이 다녀간 곳이면 멈춘다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define MAX 101
#define pp pair<int,int>
#define x first
#define y second

using namespace std;

char board[MAX][MAX];
int cloud_time[MAX][MAX];

int n, m;
queue<pp> q;

void output() {
	for (int i = 0; i < n; ++i) {
		for (int ii = 0; ii < m; ++ii)	cout << cloud_time[i][ii] << " ";
		cout << "\n";
	}
}

void solve() {
	while (!q.empty()) {
		pp cur = q.front(); q.pop();
		int ny;
		int cloud_move = 1;
		while(1) {
			ny = cur.y + cloud_move++;
			if (ny >= m)break;
			if (board[cur.x][ny] != '.' or cloud_time[cur.x][ny] != -1)break;
			cloud_time[cur.x][ny] = cloud_time[cur.x][ny - 1] + 1;
		}
	}
}

void input() {
	cin >> n >> m;
	memset(cloud_time, -1, sizeof(cloud_time));
	string line;
	for (int i = 0; i < n; ++i) {
		cin >> line;
		for (int ii = 0; ii < m; ++ii) {
			board[i][ii] = line[ii];
			if (board[i][ii] != 'c')continue;
			cloud_time[i][ii] = 0;	
			q.push({ i,ii });
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

	input();
	solve();
	output();


	return 0;
}

피드백

없음