뜸부기와 공작새

[SWEA] 1824 혁진이의 프로그래밍 검증 본문

카테고리 없음

[SWEA] 1824 혁진이의 프로그래밍 검증

성씨 2020. 5. 21. 21:13

 

#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을 리턴해야합니다.
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx&categoryId=AV4yLUiKDUoDFAUx&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

의외로 쉽지 않은 문제였는데

여러가지 풀이 방법이 있을 것 같다

내가 풀었던 방법을 정리하자면

 

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 구분하여 출력