백준[6087] 레이저 통신

아이디어

• BFS를 사용할 줄 안다.
• 다익스트라를 사용할 줄 안다.

풀이

1. 기존 다익스트라 알고리즘을 이용하되, 기준을 '꺾은 갯수' 로 표현한다.
   -> 꺾은 개수는 4가지 dy,dx를 만들고(우,밑,좌,위) 바로 옆 방향으로 옮긴다면 꺾는다고 표현한다.(ex. 현재 위 방향인데 다음 방향이 우 일경우 꺾은 개수를 1회 증가한다.) 단, 뒤로 돌아가는 것은 불가능 하기에, 이를 예외처리해준다.(본인은 (i+2)%4 를 사용하여 이 방향이 반대인지 아닌지 체크하였다.)
2. 기존 코드는 cnt가 더 작을때만 queue에 넣어주었지만, 서로 다른 방향일 수도 있기에 cnt가 같을 때도 queue에 넣어준다.
3. 다익스트라를 마친 후 최종 목적지에 대해 dp를 출력한다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <math.h>
#define MAX_VALUE 987654321
using namespace std;

char board[100][100];
vector<pair<int, int>> c;
int w, h;
int dp[100][100];

int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };

void bfs() {
	priority_queue<pair<pair<int,int>,pair<int,int>>> pq;
	int first_row = c[0].first;
	int first_col = c[0].second;

	for (int i = 0; i < 4; i++) {
		int next_row = first_row + dy[i];
		int next_col = first_col + dx[i];

		if (next_row < 0 || next_col < 0 || next_row >= h || next_col >= w) continue;
		if (board[next_row][next_col] == '*') continue;

		pq.push({{0,i},{next_row,next_col} });
		dp[next_row][next_col] = 0;
	}

	while (!pq.empty()) {
		int now_row = pq.top().second.first;
		int now_col = pq.top().second.second;
		int now_cnt = -pq.top().first.first;
		int now_dir = pq.top().first.second;
		pq.pop();

		if (dp[now_row][now_col] < now_cnt) continue;
		if (now_row == c[1].first && now_col == c[1].second) continue;

		for (int i = 0; i < 4; i++) {
			if (i == (now_dir + 2) % 4) continue;

			int next_row = now_row + dy[i];
			int next_col = now_col + dx[i];
			int next_cnt = i == now_dir ? now_cnt : now_cnt + 1;
			int next_dir = i;

			if (next_row < 0 || next_col < 0 || next_row >= h || next_col >= w) continue;
			if (board[next_row][next_col] == '*') continue;

			if (dp[next_row][next_col] >= next_cnt) {
				dp[next_row][next_col] = next_cnt;
				pq.push({ { -next_cnt,next_dir }, { next_row,next_col } });
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	 cin >> w >> h;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			char tmp; cin >> tmp;
			board[i][j] = tmp;
			if (tmp == 'C') c.push_back({ i,j });
			dp[i][j] = MAX_VALUE;
		}
	}

	dp[c[0].first][c[0].second] = 0;

	bfs();

	cout << dp[c[1].first][c[1].second];

	return 0;
}

평가

BFS와 다익스트라를 알고 있고, 이를 응용할 줄 아는지 물어보는 문제.
기존 다익스트라 알고리즘은 최단거리를 구하기 위해서 사용하는 것이지만,
이 문제는 최단거리가 아닌, 얼마나 적은 수로 꺾는가를 다익스트라로 표현해야하는
응용 문제였습니다.