[BOJ] 레이저 통신

[BOJ] 레이저 통신

Problem URL : 레이저 통신

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 987654321

using namespace std;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<string> map;
int W, H;
pair<int, int> visited[101][101]; // 레이저 위치와 방향을 동시에 기록
pair<int, int> laser[2];

struct path {
	int x, y, dir, cnt;
	path(int _x, int _y, int _dir, int _cnt) : x(_x), y(_y), dir(_dir), cnt(_cnt) {}
};

int bfs() {
	queue<path> q;
	visited[laser[0].first][laser[0].second] = { -1, INF };
	for (int nDir = 0; nDir < 4; nDir++) {
		q.push(path(laser[0].first, laser[0].second, nDir, 0));
	}
	while (!q.empty()) {
		path tmp = q.front();
		q.pop();
		int x = tmp.x;
		int y = tmp.y;
		int cnt = tmp.cnt;
		int dir = tmp.dir;
		for (int nDir = 0; nDir < 4; nDir++) {
			int nx = x + dx[nDir];
			int ny = y + dy[nDir];
			int nCnt = cnt;
			if (nx < 0 || ny < 0 || nx >= H || ny >= W || map[nx][ny] == '*') continue;
			if (dir != nDir) nCnt++;
			// 꺾은 회수가 작거나, 꺾은 회수가 같아도 방향이 다를 때 탐색 가치가 있다
			if ((visited[nx][ny].second > nCnt) || (visited[nx][ny].second == nCnt && visited[nx][ny].first != nDir)) {
				visited[nx][ny] = { nDir, nCnt };
				q.push(path(nx, ny, nDir, nCnt));
			}
		}
	}
	return visited[laser[1].first][laser[1].second].second;
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> W >> H;
	int idx = 0;
	for (int i = 0; i < H; i++) {
		string str;
		cin >> str;
		map.push_back(str);
		for (int j = 0; j < str.size(); j++) {
			if (map[i][j] == 'C') {
				laser[idx++] = { i,j };
			}
			visited[i][j] = { -1, INF };
		}
	}
	cout << bfs() << "\n";
	return 0;
}