글 읽기 - [C++] 6087 - 레이저 통신. 고수님들 한번만 도와주십쇼

hwang0108 4년 전 0

안녕하십니까 알고리즘 초보입니다.

저 나름대로 고민 많이해서 풀어보았는데, '틀렸습니다'가 나옵니다.

게시판에 올라와있는 테스트케이스 모두 해보았구요 ㅜㅜ.

제가 문제에 접근한 생각은

1. 시작지점 레이저에서 보낼 수 있는 곳으로 레이저를 보낸다.

2. 보낸 지점에서 갈 수 있는 방향(3방향)으로 보낸다.

3. 도착지점을 찾고, 사용한 거울 개수를 출력한다.

어디가 잘못된걸까요..ㅜㅜ 도움이 절실합니다.

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

//좌표 자료형
struct pos {
	int x, y;
};

struct light {
	pos l;
	int dir;
	int cnt;
};

bool operator<(light a, light b) {
	return a.cnt > b.cnt;
}

int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };

int W, H;
char map[100][100];
bool visited[100][100][4];
vector<pos> v;
int si, sj, ei, ej;
priority_queue<light> q;
int res = -1;

void bfs() {
	while (!q.empty()) {
		light cur = q.top();
		q.pop();

		/*cout << cur.l.x << " " << cur.l.y << " " << cur.cnt << "\n";*/

		for (int i = 0; i < 4; i++) {
			light nxt = cur;

			if ((nxt.dir % 2 == i % 2) && nxt.dir != i) {
				continue;
			}
			nxt.dir = i;
			nxt.l.x += di[nxt.dir];
			nxt.l.y += dj[nxt.dir];

			if (nxt.l.x < 0 || nxt.l.y < 0 || nxt.l.x >= H || nxt.l.y >= W) {
				continue;
			}

			if (nxt.l.x == ei && nxt.l.y == ej) {
				if (res == -1 || nxt.cnt < res) {
					res = cur.cnt;
				}
				continue;
			}

			if (map[nxt.l.x][nxt.l.y] != '*' && !visited[nxt.l.x][nxt.l.y][nxt.dir]) {
				visited[nxt.l.x][nxt.l.y][nxt.dir] = true;
				if (nxt.dir != cur.dir) {
					nxt.cnt++;
				}
				q.push(nxt);
			}
		}
	}
	return;
}

int main() {

	cin >> W >> H;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'C') {
				v.push_back({ i,j });
			}
		}
	}

	si = v[0].x;
	sj = v[0].y;
	ei = v[1].x;
	ej = v[1].y;

	for (int i = 0; i < 4; i++) {
		int nsi = si + di[i];
		int nsj = sj + dj[i];

		if (nsi < 0 || nsj < 0 || nsi >= H || nsj >= W) {
			continue;
		}

		if (map[nsi][nsj] != '*') {
			visited[nsi][nsj][i] = true;
			q.push({ { nsi,nsj }, i, 0 });
		}
	}

	bfs();

	cout << res;
}

wjddydgns99 4년 전 0

위 코드는 문제의 예제도 맞지 않습니다.

hwang0108 4년 전 0

죄송합니다ㅜㅜ. 다시 고민하겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] 6087 - 레이저 통신. 고수님들 한번만 도와주십쇼

hwang0108 4년 전 0

wjddydgns99 4년 전 0

hwang0108 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말