[G3] 백준 6087번 레이저 통신 C++ 다익스트라, 플러드 필

리뷰

 

https://www.acmicpc.net/problem/6087

맵 상에서 주어지는 두개의 C를 거울을 적절히 배치하여 레이저가 통하도록 하는 문제

다익스트라에서 가중치를 거리가 아닌 다른 방식으로 사용하는 것 자체가 신박한 문제였다.

 

 

전역 변수

• w, h : 맵의 가로 길이 w, 맵의 세로 길이 h
• idx : C를 구분하여 배열에 저장하기 위한 인덱스
• dx, dy : 4방향 탐색을 위한 방향 배열
• lst : 맵 정보를 문자열로 받기 위한 문자열 타입 배열
• Pos : 다익스트라 탐색을 위한 구조체, x, y좌표와 방향을 바꾼 횟수 v, 현재 방향 dir과 cmp함수를 정의한다.
• C : C의 위치 좌표를 저장하기 위한 Pos타입 배열

 

함수

1. input

void input()

 

변수와 맵 정보를 입력 받고 C정보를 초기화 하기 위한 함수

 

2. print

void print(vector<vector<int>> dist)

 

dist 벡터 디버깅을 위한 함수

 

3. dijkstra

int dijkstra(int sd)

 

다익스트라를 통해 최소 설치 거울의 개수를 찾기 위한 함수

1. 초기 탐색 방향 sd를 정수형태의 매개변수로 입력 받는다.
2. Pos타입 우선순위 큐 pq를 초기화 하고 임의의 C의 x, y좌표와 거울 변환횟수 0, 초기 방향 sd를 push한다.
3. w * h크기의 정수형 2차 벡터 dist를 매우 큰 값으로 초기화 해준다.
4. 현재 시작 위치의 dist값을 0으로 초기화 해준다.
5. pq가 빌때 까지 반복문을 실행한다, 매번 탐색마다 pq의 top에서 Pos객체를 가져와 준다.
6. 4방향 탐색을 진행하고, 만약 현재 방향과 진행 방향이 다르다면 v값을 증가시킨다.
7. 이동할 좌표의 dist보다 nv값이 작다면 값을 교체해 주고 pq에 push해준다.
8. 맵 상에서 범위를 벗어나거나 *로 표시된 지역은 방문하지 않도록 해주어야 한다.
9. 모든 탐색을 마치고 시작점 C와 다른 도착점 C의 좌표의 dist값을 리턴해 준다.

 

4. solution

int solution()

 

다익스트라의 초기 방향을 4방향으로 모두 돌려보고 정답을 리턴하는 함수

1. 정답을 출력할 ans를 매우 큰 값으로 설정해 준다.
2. 4번의 반복문을 실행하고 0 ~ 3을 dijkstra함수의 매개변수로 전달해 준다.
3. 해당 함수의 리턴값을 ans와 비교해 더 작은 값을 ans에 저장해 준다.
4. ans를 리턴한다.

 

문제풀이

1. input 함수를 통해 입력을 받아준다.
2. solution 함수를 실행하고 리턴 값을 출력해 준다.

 

참고 사항

다익스트라의 가중치는 설치한 거울의 횟수가 되어야 한다.

즉 이전 경로에 진행하던 방향과 현재 좌표로 이동한 방향이 다르다면 가중치가 증가한다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int w, h, idx;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
string lst[100];
struct Pos {
	int x, y, v, dir;
	bool operator<(const Pos& other) const {
		return v > other.v;
	}
};
Pos C[2];

void input() {
	cin >> w >> h;
	for (int i = 0; i < h; ++i) {
		cin >> lst[i];
		for (int j = 0; j < w; ++j) {
			if (lst[i][j] == 'C') C[idx++] = { i, j };
		}
	}
}

void print(vector<vector<int>> dist) {
	cout << "\n";
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			if (dist[i][j] != 1e9) cout << dist[i][j] << " ";
			else cout << '-' << " ";
		}
		cout << "\n";
	}
}

int dijkstra(int sd) {
	priority_queue<Pos> pq;
	pq.push({ C[0].x, C[0].y, 0, sd });
	vector<vector<int>> dist(h, vector<int>(w, 1e9));
	dist[C[0].x][C[0].y] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cv = pos.v, cd = pos.dir;

		for (int i = cd; i < cd + 4; ++i) {
			int nx = cx + dx[i % 4], ny = cy + dy[i % 4], nv = cv, nd = i % 4;
			if (nd != cd) nv++;
			if (0 <= nx && nx < h && 0 <= ny && ny < w && lst[nx][ny] != '*') {
				if (dist[nx][ny] > nv) {
					dist[nx][ny] = nv;
					pq.push({ nx, ny, nv, nd });
				}
			}
		}
	}
	//print(dist);
	return dist[C[1].x][C[1].y];
}

int solution() {
	int ans = 1e9;
	for (int i = 0; i < 4; i++) ans = min(ans, dijkstra(i));
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	cout << solution();
}