[백준/C++] 1175. 배달

문제 출처

www.acmicpc.net/problem/1175

1175번: 배달

문제

어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다.

입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다.

• S : 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이다.
• C : 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.
• # : 민식이가 갈 수 없는 곳이다.
• . : 민식이가 자유롭게 지나갈 수 있는 곳이다.

민식이가 한 블록 동서남북으로 이동하는데는 1분이 걸린다. 민식이는 네가지 방향 중 하나로 이동할 수 있으며, 교실을 벗어날 수 없다. 민식이가 선물을 배달해야 하는 곳에 들어갈 때, 민식이는 그 곳에 있는 사람 모두에게 선물을 전달해야 한다. 이 상황은 동시에 일어나며, 추가적인 시간이 소요되지 않는다.

민식이는 어느 누구도 자신을 보지 않았으면 하기 때문에, 멈추지 않고 매 시간마다 방향을 바꿔야 한다. 이 말은 같은 방향으로 두 번 연속으로 이동할 수 없다는 말이다. 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 교실의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 교실의 지도가 주어진다.

출력

첫째 줄에 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

 

---

풀이

이 문제가 일반적인 최단경로찾기 문제와 다른 점은 다음과 같다. 

• 같은 방향으로 연속으로 이동할 수 없다.
• 선물을 두 군데에 배달해야 한다 (두 개의 도착지를 모두 찍어야 완료)

따라서 기존의 BFS 알고리즘을 그대로 적용할 수 없어 변형이 필요했다. 

 

중복 접근이 가능하게 하면, queue가 빈 것으로 불가능 여부를 판단할 수 없다. 

(queue가 평생 비어있을 일이 없기 때문) 

따라서 "어떻게 불가능한 케이스인지를 판단하는가"가 가장 큰 걸림돌이 되었다. 

 

해당 칸에 중복 접근 횟수를 무제한이 아니라 1000, 10000 등으로 주어보았는데,

숫자가 작으면 "틀렸습니다" 

숫자가 커지면 "메모리 초과"의 결과가 나왔다. 

 

따라서 아래의 링크의 코드를 참고하여 풀었다. 

sweetday-alice.tistory.com/177

[C++][백준 2178] 미로탐색 - BFS를 이용한 최단거리

visited 배열을 사용하되, 기존에 visited[r][c] 에서 visited[r][c][방향][1번도착지점 방문 여부][2번도착지점 방문 여부] 로 케이스를 세분화해서 사용하는 방법이었다. 

 

이를 이용하기 위해서는, 지도에서 C로 표시된 두 개의 도착점을 다르게 식별할 필요가 있었다. 따라서 지도에서 하나의 C를 D로 바꾸어준 뒤 문제를 해결했다. 

 

코드 

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <memory.h>

using namespace std;

#define U 1
#define D 2
#define L 3
#define R 4

struct node {
	int x;
	int y;
	int count;
	int dir;
	int visited_C;
	int visited_D;
};

int dfs(vector<vector<char>> table, int n, int m, int startN, int startM) {
	bool visited[50][50][5][2][2];
	memset(visited, false, sizeof(visited));
	int count = -1;
	queue<node> q;
	node start = { startM, startN, 0, 0, 0, 0};
	q.push(start);
	while (!q.empty()) {
		node temp = q.front();
		q.pop();

		// 방문한 적이 있는 경우라면 pass 
		if (visited[temp.y][temp.x][temp.dir][temp.visited_C][temp.visited_D])
			continue;

		// 현재 위치가 배달지인지 확인 
		if (table[temp.y][temp.x] == 'C') 
			temp.visited_C = 1;
		if (table[temp.y][temp.x] == 'D') 
			temp.visited_D = 1;

		// 선물을 모두 배달했는지 확인
		if (temp.visited_C == 1 && temp.visited_D == 1)
			return temp.count;

		//현재 노드 방문 표시
		visited[temp.y][temp.x][temp.dir][temp.visited_C][temp.visited_D] = true; 
		
		//현재 노드에서 방문 가능한 노드 찾기 
		if (temp.dir != 1 && temp.y > 0)  // UP
			if (table[temp.y - 1][temp.x] != '#')
				q.push({ temp.x, temp.y - 1, temp.count + 1, U, temp.visited_C, temp.visited_D });
		if (temp.dir != 2 && temp.y < n - 1)  // DOWN
			if (table[temp.y + 1][temp.x] != '#')
				q.push({ temp.x, temp.y + 1,temp.count + 1, D, temp.visited_C, temp.visited_D });
		if (temp.dir != 3 && temp.x > 0)  // LEFT
			if (table[temp.y][temp.x - 1] != '#') 
				q.push({ temp.x - 1,  temp.y,temp.count + 1, L, temp.visited_C, temp.visited_D });
		if (temp.dir != 4 && temp.x < m-1)  // RIGHT
			if (table[temp.y][temp.x + 1] != '#') 
				q.push({ temp.x + 1,  temp.y,temp.count + 1, R, temp.visited_C, temp.visited_D });
	}
	return count;
}
int main(void) {
	int n, m;
	vector<vector<char>> classroom;
	int startN, startM;
	cin >> n >> m;
	int idxC = 0;
	for (int i = 0;i < n;i++) {
		string s;
		cin >> s;
		vector<char> temp(s.begin(), s.end());
		
		vector<char>::iterator iter1 = find(temp.begin(), temp.end(), 'S');
		if (iter1 != temp.end()) {
			startN = i;
			startM = distance(temp.begin(), iter1);
		}
		vector<char>::iterator iter2 = find(temp.begin(), temp.end(), 'C');
		while (iter2 != temp.end()) {
			idxC++;
			if (idxC == 2)
				temp[distance(temp.begin(), iter2)] = 'D';
			iter2 = find(iter2+1, temp.end(), 'C');
		}
		classroom.push_back(temp);
	}
	cout << dfs(classroom, n, m, startN, startM) << endl;
 	return 0;
}