[삼성 SW Expert Academy] 1824. 혁진이의 프로그램 검증 [JAVA]

| Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

---

| Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx

SW Expert Academy

---

| 풀이

1. 시뮬레이션
2. 무한루프에서 어떻게 빠져나올지 생각하는게 관건이다.
3. visited를 4차원 배열로 관리하자. [행][열][memory값][방향] -> 같은 값 + 방향으로 똑같이 와봤자 같은 꼴임.
4. 처음 시작점을 그냥 좌표 0,0 memory 값 0, direction : 3 (오른쪽) 으로 넣고 0,0부터 검사하기

---

| 어려웠던 점

1. visit 배열 관리 -> 4차원 해결
2. 처음 시작점 따로 고려해서 넣은 후에 bfs 사용하려고 하다보니 일관성 떨어지고 헷갈림. ↓ - visited도 ㅠㅠ

  3.  해결 ↓

---

| 코드

package 알고리즘공부하기;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 혁진이의프로그램검증_1824 {
	static class Status{
		int r, c, mem, dir;
		Status(int r, int c, int mem, int dir){
			this.r = r;
			this.c = c;
			this.mem = mem;
			this.dir = dir;
		}
	}
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc = 1; tc <= T; tc++) {
			int R = sc.nextInt(); // 2 ≤ R, C ≤ 20
			int C = sc.nextInt(); // 2 ≤ R, C ≤ 20
			char[][] map = new char[R][C];
			for(int i = 0; i < R; i++) {
				String line = sc.next();
				for(int j = 0; j < C; j++) {
					map[i][j] = line.charAt(j);
				}
			}
			boolean[][][][] visited = new boolean[R][C][16][4];
			Queue<Status> queue = new LinkedList<>();
			queue.add(new Status(0, 0, 0, 3));
			boolean ans = false;
			loop : while( !queue.isEmpty() ) {
				Status s = queue.poll();
				if(visited[s.r][s.c][s.mem][s.dir])
					continue;
				visited[s.r][s.c][s.mem][s.dir] = true;
				switch (map[s.r][s.c]) {
				case '@':
					ans = true;
					break loop;
				case '^':
					s.dir = 0;
					break;
				case 'v':
					s.dir = 1;
					break;
				case '<':
					s.dir = 2;
					break;
				case '>':
					s.dir = 3;
					break;
				case '_':
					s.dir = (s.mem == 0 ? 3 : 2);
					break;
				case '|':
					s.dir = (s.mem == 0 ? 1 : 0);
					break;
				case '.':
					break;
				case '+':
					s.mem = (s.mem == 15 ? 0 : s.mem + 1);
					break;
				case '-':
					s.mem = (s.mem == 0 ? 15 : s.mem - 1);
					break;
				case '?':
					for(int d = 0; d < 4; d++) {
						int nr = s.r + dr[d];
						int nc = s.c + dc[d];
						nr = ( nr == R ? 0 : nr);
						nr = ( nr == -1 ? R-1 : nr);
						nc = ( nc == C ? 0 : nc);
						nc = ( nc == -1 ? C-1 : nc);
						queue.add(new Status(nr, nc, s.mem, d));
					}
					break;
				default:
					s.mem = map[s.r][s.c] - '0';
					break;
				}
				int nr = s.r + dr[s.dir];
				int nc = s.c + dc[s.dir];
				nr = ( nr == R ? 0 : nr);
				nr = ( nr == -1 ? R-1 : nr);
				nc = ( nc == C ? 0 : nc);
				nc = ( nc == -1 ? C-1 : nc);
				queue.add(new Status(nr, nc, s.mem, s.dir));
			}
			System.out.println("#" + tc + " " + (ans ? "YES" : "NO"));
		}
	}
}

---

| 보완할 점

• 스스로 한번 풀어보기

---