BOJ - 6087번 레이저 통신(C++)

문제 출처: https://www.acmicpc.net/problem/6087

문제 난이도

Gold 4

문제 접근법

거울을 방향에 따라 놓고, 레이저 방향을 튼다고 생각하지 말자.
그냥 기존 방향과 다르게 꺾일 때 -> 거울을 놓았구나! 라고 생각하고 count + 1를 해주면 된다.

통과 코드

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

using namespace std;

int dy[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
vector<string> arr;
int W, H;
int passed[101][101];
pair<int, int> laser[2];

struct info {
	int x, y, dir, cnt;
	info(int a, int b, int d, int c) {
		x = a;
		y = b;
		dir = d;
		cnt = c;
	}
};

int bfs() {
	queue<info> q;
	passed[laser[0].first][laser[0].second] = 0;
	for (int k = 0; k < 4; k++) {
		q.push(info(laser[0].first, laser[0].second, k, 0));
	}
	while (!q.empty()) {
		info tmp = q.front();
		q.pop();
		int x = tmp.x;
		int y = tmp.y;
		int cnt = tmp.cnt;
		int dir = tmp.dir;
		for (int k = 0; k < 4; k++) {
			int nx = x + dy[k][0];
			int ny = y + dy[k][1];
			int nCnt = cnt;
			if (nx < 0 || ny < 0 || nx >= H || ny >= W || arr[nx][ny] == '*' ) continue;
			if (dir != k) nCnt++;
			if (passed[nx][ny] >= nCnt) {
				passed[nx][ny] = nCnt;
				q.push(info(nx, ny, k, nCnt));
			}
		}
	}
	return passed[laser[1].first][laser[1].second];
}


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

피드백

이거 처음에 풀 때 너무 어렵게 생각해서 알고리즘이 꼬였다. 그래서 이게 gold 4 난이도라고? 하면서 다른 사람 코드를 참고하니 내가 너무 어렵게 생각한거 였다. 문제에 집중해서 빡구현하는 것보다 가끔 센스를 발휘해 풀어야하는 법도 익숙해지자