혁진이의 프로그램 검증 [SWEA 1824][BFS][Queue][시뮬레이션]

 

[광고 누르면 오늘의 행운 상승!!]

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

SW Expert Academy

문제의 저작권은 SW Expert Academy에 있습니다.

어렵지는 않지만 구현이 귀찮고 같은 경로를 빙빙 돌기 때문에 무한루프를 빠져나갈 방법을 생각해야한다.
나는 4차원 visit배열을 사용하였다.

1. 참고사항

- 4차원 visit 배열을 사용하여 같은 메모리, 같은 방향, 같은 장소로 지나간다면 continue하였다.
- ? 를 만나면 4방향 모두로 전진시켰다.

2. 구현

- 숫자를 만난다면 메모리를 저장
- < > ^ v 를 만나면 방향 이동
- _ | 를 만난다면 3항연산자를 이용하여 방향전환
- .를 만난다면 아무것도 하지 않는다.
- +를 만난다면 1을 더하고 만약 15라면 0으로 바꾼다.
- -를 만난다면 1을 빼고 만약 0이라면 15으로 바꾼다.
- @를 만난다면 s를 "YES"로 바꾸고 종료
- ?를 만난다면 4방향으로 전진
- 4차원 visit 배열을 사용하여 같은 메모리, 같은 방향, 같은 장소로 지나간다면 continue;

- s 출력

종료

package Study9;

import java.io.*;
import java.util.*;

public class 혁진이의프로그래밍검증 {
	static class Player{
		int row, col,dir, m;
		public Player(int row, int col,int dir, int m) {
			this.row = row;
			this.col = col;
			this.dir = dir;
			this.m = m;
		}
	}
	public static int[] dx = {-1,0,1,0};
	public static int[] dy = {0,1,0,-1};
	static char[][] map;
	static boolean[][][][] visit;
	static int R,C,cnt=0;
	static String s;
	static Queue<Player> q;
	static boolean flag;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 1; tc <= T; tc++) {
			boolean tmp = false;
			st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			map = new char[R][C];
			s = "NO";
			
			visit= new boolean[16][4][20][20];
			
			for (int i = 0; i < R; i++) {
				char[] ch = br.readLine().toCharArray();
				for (int j = 0; j < C; j++) {
					map[i][j] = ch[j];
					if(map[i][j] == '@') tmp = true;
				}
			}
			if(tmp) {
				bfs();
				System.out.println("#" + tc + " " + s);
			}else System.out.println("#" + tc + " " + "NO");
		}
	}
	private static void bfs() {
		q = new LinkedList<>();
		q.add(new Player(0,0,1,0));
		
		while(!q.isEmpty()) {
			Player p = q.poll();
			
			if(!visit[p.m][p.dir][p.row][p.col]) {
				visit[p.m][p.dir][p.row][p.col] = true;
				q.add(new Player(p.row,p.col,p.dir,p.m));
			}else continue;
			
			flag = false;
			
			if(map[p.row][p.col]-'0' >= 0 && map[p.row][p.col]-'0' <= 9) {
				p.m = map[p.row][p.col]-'0';
			}
			else {
				switch(map[p.row][p.col]) {
				case '<': p.dir = 3; 						break;
				case '>': p.dir = 1; 						break;
				case '^': p.dir = 0; 						break;
				case 'v': p.dir = 2; 						break;
				case '_': p.dir = p.m==0?1:3;				break;
				case '|': p.dir = p.m==0?2:0;				break;
				case '?': flag = true;					    break;
				case '.': 								    break;
				case '@': s = "YES"; 						return;
				case '+': if(p.m == 15) p.m  = 0;
				else                              p.m += 1; break;
				case '-': if(p.m == 0)  p.m  = 15;
				else 						      p.m -= 1; break;
				}
			}
			
			if(flag) {
				for (int i = 0; i < 4; i++) {
					int nx = p.row + dx[i];
					int ny = p.col + dy[i];
					
					if(nx < 0)		 nx = R-1;
					else if(nx >= R) nx = 0;
					else if(ny < 0)  ny = C-1;
					else if(ny >= C) ny = 0;
					
					q.add(new Player(nx,ny,i,p.m));
				}
			}else {
				int nx = p.row + dx[p.dir];
				int ny = p.col + dy[p.dir];
				
				if(nx < 0)		 nx = R-1;
				else if(nx >= R) nx = 0;
				else if(ny < 0)  ny = C-1;
				else if(ny >= C) ny = 0;
				
				q.add(new Player(nx,ny,p.dir,p.m));
			}
		}
	}
}