👀 문제 설명
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을 출력한다.
예제 입력 1
3 4
c . . c
. . c .
. . . .
예제 출력 1
0 1 2 0
-1 -1 0 -1
-1 -1 -1 -1
예제 입력 2
6 8
. c . . . . . .
. . . . . . . .
. c c c . . c .
. . . . c . . .
. . c . c c . .
. . . . 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 3
힌트
입출력 예제 1에서는, JOI시가 3 × 4 개의 작은 구역으로 나뉘어 있다. 지금 JOI시의 구름 상황은 아래와 같다. 그림의 위쪽이 북쪽이다.
1분 간격으로 구름은 다음과 같이 움직인다.
✍🏻풀이
2차원 벡터 JOI와 cloud를 선언하고, JOI 벡터를 입력받는다.
JOI 벡터를 탐색하며 c인 위치의 cloud값은 0으로 바꾼다.
j가 1보다 크거나 같은 경우에 cloud[i][j - 1]의 값이 0보다 크거나 같으면 cloud[i][j]의 값은 cloud[i][j - 1] + 1이 된다.
필요한 변수
vector<vector<char>> JOI : JOI 시의 구름 위치를 표현한 벡터
vector<vector<int>> cloud : 몇 분 후에 해당 위치에 구름이 뜨는지 저장하는 벡터
int H, W : JOI 시의 H, W값
알고리즘
1. H, W 값을 입력받고, JOI 벡터와 cloud 벡터의 사이즈를 초기화한 후, JOI 벡터를 입력받는다.
2. JOI 벡터를 탐색한다.
2-1. JOI[i][j]의 값이 c라면 cloud[i][j]를 0으로 바꾼다.
2-2. j가 1보다 크거나 값고, cloud[i][j - 1]이 0보다 크거나 같으면 cloud[i][j]를 cloud[i][j - 1] + 1 값으로 바꾼다.
코드
//
// BOJ_10709.cpp
// Algorithm
//
// Created by 조수민 on 2020/07/14.
// Copyright © 2020 조수민. All rights reserved.
//
// 기상캐스터(https://www.acmicpc.net/problem/10709)
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
vector<vector<char>> JOI;
vector<vector<int>> cloud;
void input()
{
int H, W;
// input H, W
cin >> H >> W;
// resizing vector
JOI.resize(H);
cloud.resize(H);
for (int i = 0; i < H; i++)
{
JOI[i].resize(W);
cloud[i].resize(W);
cloud[i].assign(cloud[i].size(), -1); // cloud 벡터를 -1로 초기화
}
// input JOI vector
for (int i = 0; i < JOI.size(); i++)
for (int j = 0; j < JOI[i].size(); j++)
cin >> JOI[i][j];
}
void getCloudTime()
{
for (int i = 0; i < JOI.size(); i++)
for (int j = 0; j < JOI[i].size(); j++)
{
if (JOI[i][j] == 'c') // JOI[i][j]가 c라면
cloud[i][j] = 0; // cloud[i][j]를 0으로 바꾼다.
else if (j >= 1 && (cloud[i][j - 1] >= 0)) // cloud[i][j - 1]이 0보다 크거나 같으면
cloud[i][j] = cloud[i][j - 1] + 1; // cloud[i][j]를 그 전 값에 +1한다.
}
}
void output()
{
for (int i = 0; i < cloud.size(); i++)
{
for (int j = 0; j < cloud[i].size(); j++)
cout << cloud[i][j] << " ";
cout << endl;
}
}
int main()
{
input(); // input
getCloudTime(); // cloud vector 구하기
output(); // output
return 0;
}
'숨막히는 알고말고 > 문제 풀이' 카테고리의 다른 글
[Baekjoon] 홍준 프로그래밍 대회(BOJ 1222) (0) | 2020.08.31 |
---|---|
[Baekjoon] 추월(BOJ 2002) (0) | 2020.07.23 |
[Baekjoon] 피보나치 수의 확장(BOJ 1788) (0) | 2020.07.15 |
[Baekjoon] 정상회담 2(BOJ 1670) (0) | 2020.07.15 |
[Baekjoon] 토너먼트(BOJ 1057) (0) | 2020.06.23 |