[SWEA] 1824. 혁진이의 프로그램 검증

문제

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

SW Expert Academy

풀이

* dfs를 이용해서 탐색을 진행한다. 

* @를 만나면 flag 를 True로 만들고 탐색을 종료한다. 

* 갔던 곳을 또 가지 않도록 방문 표시를 한다. 

하지만, 프로그램 상 메모리에 있는 값에 따라 다른 처리를 하는 연산이 있기 때문에 

visited 배열에 방문했던 당시의 메모리값(buf)을 저장하고, 

? 인 경우에는 네 방향 모두를 한 번에 방문하기 때문에 방향도 같이 저장을 해 둔다. 

 

 

#include <iostream> #include <vector> #include <cstring> using namespace std; //SWEA 1824. 혁진이의 프로그램 검증 //https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx&categoryId=AV4yLUiKDUoDFAUx&categoryType=CODE int r, c; char map[21][21]; bool visited[21][21][4][16]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; int buf = 0; bool flag = false; void dfs(int x, int y, int dir) { if (map[x][y] == '@') { flag = true; return; } else if (map[x][y] == '^' || (map[x][y] == '|' && buf)) dir = 0; else if (map[x][y] == 'v' || (map[x][y] == '|' && !buf)) dir = 1; else if (map[x][y] == '<' || (map[x][y] == '_' && buf)) dir = 2; else if (map[x][y] == '>' || (map[x][y] == '_' && !buf)) dir = 3; else if ('0' <= map[x][y] && map[x][y] <= '9') buf = (map[x][y] - '0'); else if (map[x][y] == '+') buf = buf == 15 ? 0 : buf + 1; else if (map[x][y] == '-') buf = buf == 0 ? 15 : buf - 1; if (visited[x][y][dir][buf]) return; visited[x][y][dir][buf] = true; if (map[x][y] == '?') { for (int i = 0; i < 4; i++) { int nx = (x + dx[i] + r) % r; int ny = (y + dy[i] + c) % c; dfs(nx, ny, i); } } else { int nx = (x + dx[dir] + r) % r; int ny = (y + dy[dir] + c) % c; dfs(nx, ny, dir); } } void init() { memset(map, 0, sizeof(map)); memset(visited, 0, sizeof(visited)); flag = false; buf = 0; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int tc = 1; tc <= t; tc++) { cin >> r >> c; init(); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cin >> map[i][j]; } } //처음 이동방향은 오른쪽 dfs(0, 0, 3); cout << "#" << tc << " "; if (flag) cout << "YES" << '\n'; else cout << "NO" << '\n'; } return 0; }