[C++] G5 백준 3987 - 보이저 1호

1. 문제 링크

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

소요 시간 : 1시간 30분

시도 횟수 : 1

 

2. 문제 설명

난이도 : G5

사용 알고리즘 : 구현, 시뮬레이션

우주를 떠도는 보이저 1호,,그의 시그널이 오래 머무는 시간을 알아내는 문제

 

3. 풀이 방식

로직은 복잡하지 않았다. 근데 별 하찮은 실수들 때문에 개고생을 했다(if 조건문에 a=b로 했다던지,,,)

무한히 도는 경우를 확인하기 위해 map을 사용했다(<좌표, bool>)

방향 정보를 dir이라는 변수에 저장하고 이동한 뒤 '/' 혹은 '\'를 만나면 방향을 바꿔주는 방식!

 

#include<iostream>
#include<string>
#include<map>

using namespace std;

int n, m;
int space[501][501];
map<pair<int, int>, bool> isvisit;


int loc(int a, int b) { return (a * m + b - n); }

int travel(int pr, int pc, int dir) {
	if (space[pr][pc] == 1) return 0;
	isvisit.clear();
	int dist = 1;
	int r = pr, c = pc;
	while (1) {
		if (isvisit[{ loc(r, c), dir }]) {
			dist = -1;
			break;
		}
		isvisit[{loc(r, c), dir}] = true;
		if (dir == 0) {//UP
			r -= 1;
			if (r == 0 || space[r][c] == 1) break;
			else if (space[r][c] == 2) {// '/'
				dir = 1;
			}
			else if (space[r][c] == 3) {// '\'
				dir = 3;
			}
		}
		else if (dir == 1) {//RIGHT
			c++;
			if (c > m || space[r][c] == 1) break;
			if (space[r][c] == 2) {// '/'
				dir = 0;
			}
			else if (space[r][c] == 3) {// '\'
				dir = 2;
			}
		}
		else if (dir == 2) {//DOWN
			r++;
			if (r > n || space[r][c] == 1) break;
			if (space[r][c] == 2) {// '/'
				dir = 3;
			}
			else if (space[r][c] == 3) {// '\'
				dir = 1;
			}
		}
		else {//LEFT
			c--;
			if (c == 0 || space[r][c] == 1) break;
			if (space[r][c] == 2) {// '/'
				dir = 2;
			}
			else if (space[r][c] == 3) {// '\'
				dir = 0;
			}
		}
		dist++;
	}
	return dist;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= m; j++) {
			switch (s[j - 1]) {
			case '.':
				space[i][j] = 0;
				break;
			case 'C':
				space[i][j] = 1;
				break;
			case '/':
				space[i][j] = 2;
				break;
			case '\\':
				space[i][j] = 3;
				break;
			}
		}
	}

	int pr, pc;
	cin >> pr >> pc;
	
	int ans_dist = 0;
	char ans_dir;
	for (int i = 0; i < 4; i++) {//위, 오른쪽, 아래, 왼쪽 순서
		int res = travel(pr, pc, i);
		if (res == -1) {
			if (i == 0) ans_dir = 'U';
			else if (i == 1) ans_dir = 'R';
			else if (i == 2) ans_dir = 'D';
			else ans_dir = 'L';
			cout << ans_dir << "\nVoyager";
			return 0;
		}
		if (res > ans_dist) {
			ans_dist = res;
			if (i == 0) ans_dir = 'U';
			else if (i == 1) ans_dir = 'R';
			else if (i == 2) ans_dir = 'D';
			else ans_dir = 'L';
		}
	}
	cout << ans_dir << "\n" << ans_dist;
}

 

<오늘의 TMI>
에버랜드의 사막여우 인형이 날 항상 쳐다보고 있다.
저친구 꽤나 귀여움