일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 커널 패킷 처리
- 네트워크 스택
- Python
- 도커
- pyqt menu bar
- git
- 3D Surface Area
- 리눅스 커널
- pyqt status bar
- tcp stack
- 해커랭크
- 혁진이의 프로그램 검증
- git 명령어
- 두 문자열
- 프로그래밍 문제
- pyqt button
- 백준 알고리즘
- git 입문
- 하이퍼바이저
- SWEA
- 회문
- 17609
- pyqt layout
- hackerrank
- PyQt
- Queen's Attack II
- pyqt tooltip
- Two Characters
- Queen's Attack
- 백준
- Today
- Total
뜸부기와 공작새
[SWEA] 1824 혁진이의 프로그래밍 검증 본문
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
typedef struct {
int r;
int c;
char size;
} map_t;
int R, C;
int path[21][21][16][4];
int dr[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };
map_t map[21][21];
vector<map_t> v;
vector<map_t> atv;
int dfs(int posr, int posc, int mem, int dir, int depth) {
if (posr >= R) posr = 0;
else if (posr < 0) posr = R - 1;
if (posc >= C) posc = 0;
else if (posc < 0) posc = C - 1;
path[posr][posc][mem][dir]++;
if (depth >= R * C * 50 || path[posr][posc][mem][dir] > 3) {
return 0;
}
if (map[posr][posc].size == '?') {
for (int i = 0; i < 4; i++) {
dir = i;
if (dfs(posr + dr[dir], posc + dc[dir], mem, dir, depth + 1) == 1) {
return 1;
}
}
}
else {
switch (map[posr][posc].size) {
case '<': dir = 2; break;
case '>': dir = 0; break;
case '^': dir = 3; break;
case 'v': dir = 1; break;
case '_': mem == 0 ? dir = 0 : dir = 2; break;
case '|': mem == 0 ? dir = 1 : dir = 3; break;
case '.': break;
case '@': { return 1; break; }
case '+': mem++; if (mem == 16) mem = 0; break;
case '-': mem--; if (mem == -1) mem = 15; break;
case '0': mem = 0; break; case '1': mem = 1; break; case '2': mem = 2; break;
case '3': mem = 3; break; case '4': mem = 4; break; case '5': mem = 5; break;
case '6': mem = 6; break; case '7': mem = 7; break; case '8': mem = 8; break;
case '9': mem = 9; break;
default: break;
}
if (dfs(posr + dr[dir], posc + dc[dir], mem, dir, depth + 1) == 1) {
return 1;
}
}
return 0;
}
int check_at() {
for (int i = 0; i < atv.size(); i++) {
if (!(map[atv[i].r + 1][atv[i].c].size == '>' || map[atv[i].r + 1][atv[i].c].size == '<')) return 1;
if (!(map[atv[i].r - 1][atv[i].c].size == '>' || map[atv[i].r - 1][atv[i].c].size == '<')) return 1;
if (!(map[atv[i].r][atv[i].c - 1].size == '^' || map[atv[i].r][atv[i].c - 1].size == 'v')) return 1;
if (!(map[atv[i].r][atv[i].c + 1].size == '^' || map[atv[i].r][atv[i].c + 1].size == 'v')) return 1;
}
return 0;
}
int main(int argc, char** argv) {
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; ++test_case) {
cin >> R >> C;
v.clear(); atv.clear();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
map[i][j].r = i; map[i][j].c = j;
cin >> map[i][j].size;
if (map[i][j].size == '?') {
v.push_back(map[i][j]);
}
if (map[i][j].size == '@') {
atv.push_back(map[i][j]);
}
}
}
if (atv.size() == 0) {
cout << '#' << test_case << " NO\n";
continue;
} else {
if (check_at() == 0) {
cout << '#' << test_case << " NO\n";
continue;
}
}
int ans;
ans = dfs(0, 0, 0, 0, 0);
if (ans == 1) cout << '#' << test_case << " YES\n";
else cout << '#' << test_case << " NO\n";
memset(path, 0, sizeof(path));
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
의외로 쉽지 않은 문제였는데
여러가지 풀이 방법이 있을 것 같다
내가 풀었던 방법을 정리하자면
1. 입력 받고
2. 입력이 ?인 경우 ?전용 벡터에 push_back()
3. 입력이 @인 경우 @전용 벡터에 push_back()
4. @문자를 입력하지 않은 경우 출구가 없는 map이므로 무조건 no 출력
5. 입력받은 @문자들을 모두 확인해본다
(@문자 상하좌우로 방향 문자가 있는지 있다면 이 문자들로 인해서 @문자에 도달할 수 없는 조건을 형성하고 있는지)
(입력받은 모든 @문자들이 방향문자로 감싸져있는경우 @문자에 도달할 수 없으므로 No 출력)
6. 최초 원점(0, 0) 좌표를 재귀함수 인자로 전달하여 시뮬레이션 시작
7. 현재 map의 값이 ?가 아닌 경우에는 문제에 주어진 조건대로 좌표이동, 메모리 변경 등을 수행해주고
재귀함수를 호출하며 이때 좌표는 방향만큼 이동한 좌표를 인자로 넘겨줌
8. 시뮬레이션 함수에서는 현재 map의 값이 ?인 경우
완전탐색으로 4가지 모든 방향으로 각각 좌표 바꿔주며 재귀를 호출해준다
9. (종료조건) (이거는 조금 안맞는 방법인 것 같은데) 완전탐색함수 종료조건은 세가지
첫번째) 재귀호출 depth가 맵 크기 * K (상수) 번째 이상인 경우 (나같은 경우에는 눈떄중으로 50으로 줬음)
두번째) 해당 map의 좌표와 그때 메모리 값, 방향 값을 의미하는 visit 변수를 만들어 놓았는데
재귀호출했을 때 visit 값이 3이상인 경우 ("동일한 조건의 사이클이 3번 이상 반복될 경우" 의 의미로 만든 visit)
두 번째 조건은 처음 구현할떄는 생각하지 못했는데 SWEA 문제 댓글보고 아이디어를 가져왔음... 굳
세번쨰) @를 만났을 때 ... 이때는 리턴값을 달리 해서 YES 출력 조건 리턴값으로 함수종료
10. 시뮬레이션 종료 후 리턴값을 보고 YES, NO 구분하여 출력