[SWEA/C++] 1249. [S/W 문제해결 응용] 4일차 - 보급로(D4)

풀이 시간: 1h48m46s

시간 복잡도: O(N^2)

공간 복잡도: O(N^2)

참고 자료: https://coooding.tistory.com/32

문제

2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다.

전투가 진행중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다.

그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지날 갈 수 없다.

전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다.

공병대는 출발지(S) 에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다.

도로가 파여진 깊이에 비례해서 복구 시간은 증가한다.

출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오.

깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다.

그림 1  (a) 파손된 도로  (b) 지도 형태와 이동 방향

지도 정보는 그림1(b)와 같이 2차원 배열 형태로 표시된다.

출발지는 좌상단의 칸(S)이고 도착지는 우하단의 칸(G)가 된다.

이동 경로는 상하좌우 방향으로 진행할 수 있으며, 한 칸씩 움직일 수 있다.

지도 정보에는 각 칸마다 파여진 도로의 깊이가 주어진다. 현재 위치한 칸의 도로를 복구해야만 다른 곳으로 이동할 수 있다.

그림 2 지도 정보

이동하는 시간에 비해 복구하는데 필요한 시간은 매우 크다고 가정한다.

따라서, 출발지에서 도착지까지 거리에 대해서는 고려할 필요가 없다.

지도 정보는 그림2에서 보듯이 2차원 배열의 형태이다.

출발지(S)와 도착지(G)는 좌상단과 우하단이 되고 입력 데이터에서는 0으로 표시된다.

출발지와 도착지를 제외한 곳이 0인 것은 복구 작업이 불필요한 곳이다.

다음과 같은 지도에서 복구 작업 시간이 최소인 시간은 2이고 회색으로 칠해진 경로가 된다.

입력

가장 첫 줄은 전체 테스트케이스의 수이다.

각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.

그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.

출력

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다.

이때 C는 케이스의 번호이다.

같은 줄에 빈 칸을 하나 두고, 주어진 입력에서 출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오.

문제 풀이

오류 원인

처음에 배열 받을 때 다음과 같이 코드를 작성해서 입력 오류가 계속 발생했다.

// 이전 입력값 받는 코드
for (int j = 0; j < N; j++)
	for (int k = 0; k < N; k++)
		cin >> grid[j][k];

 

cin 같은 경우에는 공백 문자나 개행 문자가 입력되기 전까지의 모든 값을 한 번에 입력 받기 때문에, 실제 예제 입력을 사용했을 때 배열의 한 줄을 통채로 받기 때문에 위와 같은 코드는 오류가 발생할 수 밖에 없다.

실제로 위의 코드는 각 좌표값의 복구 시간 하나씩 입력받는 형태로 되어있기 때문에 오류가 발생한다.

 

따라서 아래와 같이 string 변수를 새로 선언하여 한 줄 전체를 문자열로 받아 처리하였다.

문자열로 받은 s를 각각 한자리씩 떼어내어 grid의 해당하는 좌표값에 하나씩 삽입하였다. 

이때, s[k]는 string이기 때문에 '0'의 ASCII 코드 값을 빼서 해당 문자(string)에 해당하는 숫자(int)로 변환하는 작업을 해주었다.

// 지도 크기 N 만큼 2차원 배열 형태의 지도 정보 입력
for (int j = 0; j < N; j++) {
    string s; // 한 줄 전체를 문자열로 받아서 처리
    cin >> s;
    for (int k = 0; k < N; k++) {
        // '0'의 ASCII 코드 값을 빼서 해당 문자에 해당하는 숫자로 변환
        grid[j][k] = s[k] - '0';
    }
}

전체 코드

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#define INF 1e6
#define MAX 101
using namespace std;

int N;
int grid[MAX][MAX];
int recoveryTime[MAX][MAX]; // 각 위치별 누적된 최소 복구 시간 값을 저장하는 배열
bool visited[MAX][MAX];
int dist[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };

int bfs() {
	queue<pair<int, int>> q;
	q.push({ 0, 0 }); // 출발점 큐에 삽입
	visited[0][0] = true; // 첫번째 노드 방문 처리
	recoveryTime[0][0] = 0; // 출발점은 누적 복구 시간이 0

	while (!q.empty()) {
		// 현재 좌표 값
		int curX = q.front().first;
		int curY = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			// 다음 좌표값 설정
			int nextX = curX + dist[i][0];
			int nextY = curY + dist[i][1];

			// 그래프 범위 내에 있는지 확인
			if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;

			/**
			* 다음 좌표를 아직 방문하지 않았거나,
			* (현재 누적 복구 시간 값 + 다음 좌표의 복구 시간 값)이
			* (다음 좌표의 누적 복구 시간 값)보다 작은 경우 갱신
			* 초기에는 (다음 좌표의 누적 복구 시간 값)이 INF로 초기화되어 있음
			* 그 이후에는 누적 복구 시간 값이 더 작은 값으로 계속 갱신됨
			*/
			if (!visited[nextX][nextY] 
				|| recoveryTime[nextX][nextY] > recoveryTime[curX][curY] + grid[nextX][nextY]) {
				recoveryTime[nextX][nextY] = recoveryTime[curX][curY] + grid[nextX][nextY];
				q.push({ nextX, nextY });
				visited[nextX][nextY] = true;
			}
		}
	}
	return recoveryTime[N - 1][N - 1];
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int C;
	cin >> C;
	for (int i = 1; i <= C; ++i) {
		memset(visited, false, sizeof(visited)); // 방문여부 전부 false로 초기화
		memset(recoveryTime, INF, sizeof(recoveryTime)); // 누적 복구 시간 INF로 초기화
		cin >> N;

		// 지도 크기 N 만큼 2차원 배열 형태의 지도 정보 입력
		for (int j = 0; j < N; j++) {
			string s; // 한 줄 전체를 문자열로 받아서 처리
			cin >> s;
			for (int k = 0; k < N; k++) {
				// '0'의 ASCII 코드 값을 빼서 해당 문자에 해당하는 숫자로 변환
				grid[j][k] = s[k] - '0';
			}
		}

		cout << "#" << i << " " << bfs() << "\n";
	}
}

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy