https://www.acmicpc.net/problem/3987
3987번: 보이저 1호
문제 보이저 1호는 1977년에 발사된 NASA의 태양계 무인 탐사선이다. 현재 보이저 1호는 태양권덮개 (헬리오시스)에 있다. 보이저 1호와 같이 오랜 기간동안 활동하는 탐사선은 경로를 항성계를 만날 때 마다 라디오 시그널 메시지를 이용해서 기록하고 있다. 항성계를 N * M개의 직사각형으로 나누어져 있는 N행 M열의 직사각형 그리드라고 생각해보자. 각 칸은 행성, 블랙홀을 포함할 수 있으며, 비어있을 수도 있다. 탐사선은 인접한 네 칸(위, 아래, 오
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include<stdio.h>
#include<string.h>
#define NSIZE 501
#define MSIZE 501
using namespace std;
char input[NSIZE][MSIZE];
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
int N, M;
int y, x;
int Max = 0x80000000;
char Maxdir;
int flag = 1;
int chk[NSIZE][NSIZE][4];
void init() {
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf(" %1c",&input[i][j]);
}
}
scanf("%d %d", &y, &x);
y -= 1;
x -= 1;
}
void signal() {
for (int dir = 0; dir < 4; dir++) {
int ny = y;
int nx = x;
int ndir = dir;
int cnt = 1;
flag = 0;
int c = 0;
memset(chk, 0, sizeof(chk));
while (1) {
ny += dy[ndir]; nx += dx[ndir];
if (chk[ny][nx][ndir] == 1) {
if (dir == 0) Maxdir = 'U';
else if (dir == 1)Maxdir = 'R';
else if (dir == 2)Maxdir = 'D';
else if (dir == 3)Maxdir = 'L';
printf("%c\nVoyager\n", Maxdir);
flag = 1;
break;
}
chk[ny][nx][ndir]++;
if (0 <= ny && ny < N && 0 <= nx && nx < M) {
if (input[ny][nx] == 'C') break;
else if (input[ny][nx] == '/') {
if (ndir == 0) ndir = 1;
else if (ndir == 1) ndir = 0;
else if (ndir == 2)ndir = 3;
else if (ndir == 3)ndir = 2;
}
else if (input[ny][nx] =='\\') {
if (ndir == 0) ndir = 3;
else if (ndir == 1) ndir = 2;
else if (ndir == 2)ndir = 1;
else if (ndir == 3)ndir = 0;
}
}
else {
break;
}
cnt++;
}
if (flag) {
return;
}
if (Max < cnt) {
Max = cnt;
if (dir == 0) Maxdir = 'U';
else if (dir == 1)Maxdir = 'R';
else if (dir == 2)Maxdir = 'D';
else if (dir == 3)Maxdir = 'L';
}
}
}
int main(void) {
init();
signal();
if (flag != 1) {
printf("%c\n%d", Maxdir, Max);
}
return 0;
}
|
이문제는 접했을때 출발 위치를 정해줘서 쉽다 생각했는데 좀 애를 먹었습니다. 경우를 잘주었다 생각했었는데
무한 반복적으로 시그널이 반복이 되는 경우에서 실수가 있었습니다.
처음에는 배열에 'S'라고 새겨놓고 시그널이 돌다가 다시 S를 만나면 즉 출발위치에 다시 오게되면 반복되는 경우
라고 생각했었는데 정말 찝찝했긴 했는데 설마가 정말 사람 여럿 잡습니다.
이렇게 다음에는 실수 하지않기위해 공부하는거니까요. 그래도 앞으로는 실수 없이 해겠습니다.
그래서 이걸 어떻게 해결했나 들어오는 방향이 다른경우가 출발점을 지날수 있기때문에 삼차원 배열을 사용하여
같은 위치라도 같은 방향으로 지나가게되면 그경우를 무한반복인 경우로 해서 조건을 주고 걸러주었습니다.
글로써는 이해가 안될 수 있기 때문에 그림으로 간단히 설명해드리자면
그림을 발로 그린것은 아니지만 대게 삐뚤뺴뚤하네요. 그림은 설명을 위한것일뿐 o 을 보시면 처음 제가 했던 방식으로 하게된다면 저렇게 위방향부터 시작을 했을때 저렇게 3번이나 지나가는데 무조건 무한반복이라고 생각을 해버려서
틀린거죠 그래서
사차원배열을 이용해서
chk [ 1 ][ 1 ] [ 위 ] = 1
chk [ 1 ][ 1 ] [ 아래 ] = 1
chk [ 1 ][ 1 ] [ 오른쪽 ] = 0
chk [ 1 ][ 1 ] [ 왼쪽 ] = 1
이라서 처음에는 0이였다가 바뀌는것이기때문에 탈출시의 조건으로 빠지게되고
이렇게 배치가 되어있었다 하면
chk [ 1 ][ 1 ] [ 위 ] = 1
chk [ 1 ][ 1 ] [ 아래 ] = 1
chk [ 1 ][ 1 ] [ 오른쪽 ] = 0
chk [ 1 ][ 1 ] [ 왼쪽 ] = 1
이미 이상태에서 검은것이 하늘색 원 부분으로 가면 이미 아래쪽이 1로 되어있으므로 이경우는
무한 voyager을 출력하시면 됩니다. 정말 쉽죠
이렇게 삼차원 체크에대해서 알려드릴수 있었네요 오늘은 여기까지 입니다.
내일도 즐거운 알고리즘 하세요.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 2468 안전영역 (0) | 2019.09.17 |
|---|---|
| 백준 1938 통나무 옮기기 (0) | 2019.09.11 |
| 백준 2174 로봇 시뮬레이션 (0) | 2019.09.09 |
| 백준 2529 부등호 (0) | 2019.09.09 |
| 백준 3055 탈출 (0) | 2019.09.09 |
댓글