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

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

SW Expert Academy

---

1. 문제 요약

수행명령대로 이동한다, 정지할 수 있으면 YES, 정지할 수 없다면 NO를 출력한다.

 

2. 풀이

22.11.13 - BFS 풀이

BFS 로 풀었다.

처음에 DFS로 풀다가 터져서 접고 BFS로 바꿔서 풀었더니 자꾸 테케 65/69만 떴다

(친구는 DFS로 풀었다. 오늘 캠퍼스 가서 DFS로 풀어볼 것이다. 풀이 올리겠음)

테케 4개가 통과 못한 이유는 ? 녀석 때문이다

4방향의 경우를 봐야하기 때문에 한 방향 봤다가 원복을 시켜줘야 한다.

 

1. 메모리 크기를 원복시켜주지 않았다.

=> 원복시키는데 까다로우니까 그냥 클래스에 추가해서 들고다니게 했다.

2. 방문할 때 y좌표, x좌표, 방향 그리고 메모리크기에 따라 방문 지점이 달라진다.

=> 메모리 크기에 따라 방향이 바뀔 수 있기 때문이다. 그래서 visited를 4차원으로 해줘야 한다. visited[y][x][d][mem]

3. 방문한 지점을 또 방문했을 때 바로 return 해주면 안된다.

=> 4방향을 봐야하기 때문에 continue해서 다음 방향으로 넘어가야 한다.

나는 한 방향만 보고 return해줬기 때문에 당연히 틀린 답이었다. 

 

 

22.11.15 - DFS 풀이

DFS(백트래킹) 으로 풀었다.

기저조건은 

1) @일 때 (=> 상태 true로 바꿔주고 리턴, 답YES)

2) visited[y][x][방향][메모리값] 을 재방문할 때 (=> 그냥 리턴 => 결국 상태 false, 답NO)

 

내가 놓친 부분은

1. visited를 4차원으로 해야한다.

   => visited[y][x][방향][메모리값]

2. ?를 만났을 때 4방을 보기 위해 dfs가 끝나면 visited 현재상태를 false로 바꿔줘야 한다.

3. 입력 값에 @가 없을 경우, 멈추지 못한다.

   => 바로 NO 출력하고 리턴해줘야 한다.

 

 

DFS, BFS 실행 시간은 큰 차이가 없다. 

나에겐 보통녀석이 아니었음

 

3. 코드

BFS

package a22_11_13;

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

public class SW_1824_혁진이의프로그램검증 {

	static char[][] map;
	static int R,C;
	static boolean isStop;
	static boolean[][][][] visited;
	
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine());
		for (int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			map = new char[R][C];
			visited = new boolean[R][C][4][16];
			
			for (int i=0; i<R; i++) {
				String s = br.readLine();
				for (int j=0; j<C; j++) {
					map[i][j] = s.charAt(j);
				}
			} //입력 끝
			
			isStop=false;
			bfs();
			if (isStop==false) System.out.println("#"+tc+" "+"NO");
			else System.out.println("#"+tc+" "+"YES");
		}
	}
	
	static void bfs() {
		Queue<Pos> queue = new ArrayDeque<> ();
		if (map[0][0] >= '0' && map[0][0] <= '9') {
			queue.offer(new Pos(0,0,3,map[0][0]-'0'));
		}
		else queue.offer(new Pos(0,0,3,0));
		
		while (!queue.isEmpty()) {
			Pos cur = queue.poll();
			int y = cur.y;
			int x = cur.x;
			int d = cur.d;
			int mem = cur.mem;
			if (map[y][x]=='@') {
				isStop = true;
				return;
			}

			if (map[y][x] >= '0' && map[y][x] <= '9') {
				mem = map[y][x]-'0';
			}
			
			if (visited[y][x][d][mem] == true) continue; //return으로 다른 방향은 못보고 바로끝내버려서 틀림
			visited[y][x][d][mem] = true;
			
			if (map[y][x]=='?') {
				for (int rand=0; rand<4; rand++) {
					int ny = y+dy[rand];
					int nx = x+dx[rand];
					if (ny<0) ny=R-1;
					else if (ny>=R) ny=0;
					else if (nx<0) nx=C-1;
					else if (nx>=C) nx=0;
					queue.offer(new Pos(ny, nx, rand, mem));
				}
			}
			else {
				
				if (map[y][x]=='^') d=0;
				else if (map[y][x]=='v') d=1;
				else if (map[y][x]=='<') d=2;
				else if (map[y][x]=='>') d=3;

				else if (map[y][x]=='_') {
					if (mem==0) d=3;
					else d=2;
				}
				else if (map[y][x]=='|') {
					if (mem==0) d=1;
					else d=0;
				}
				else if (map[y][x]=='@') {
					isStop = true;
					return;
				}
				else if (map[y][x]=='+') {
					if (mem==15) mem=0;
					else mem++;
				}
				else if (map[y][x]=='-') {
					if (mem==0) mem=15;
					else mem--;
				}
				
				int ny = y+dy[d];
				int nx = x+dx[d];
				if (ny<0) ny=R-1;
				else if (ny>=R) ny=0;
				else if (nx<0) nx=C-1;
				else if (nx>=C) nx=0;
				queue.offer(new Pos(ny, nx, d, mem));
			}
		}
	}

	static class Pos {
		int y, x, d, mem; //?방향마다 mem값이 바뀔 수 있으므로 전역으로 하면 안되고 들고다녀야 함
		Pos(int y, int x, int d, int mem) {
			this.y = y;
			this.x = x;
			this.d = d;
			this.mem = mem;
		}
	}
}

DFS

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

public class SW_1824_혁진이의프로그램검증 {

	static int R,C;
	static char[][] map;
	static boolean isStop;
	static boolean[][][][] visited;
	
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for (int tc=1; tc<=T; tc++) {
			st = new StringTokenizer(br.readLine());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			map = new char[R][C];
			visited = new boolean[R][C][4][16];
			
			boolean isOk = false;
			for (int i=0; i<R; i++) {
				String s = br.readLine();
				for (int j=0; j<C; j++) {
					map[i][j] = s.charAt(j);
					if (map[i][j] == '@') isOk = true;
				}
			} //입력 끝
			
			if (isOk == false) {
				System.out.println("#"+tc+" NO");
				continue;
			}
			
			isStop = false;
			System.out.print("#"+tc+" ");
			if (map[0][0]>='0' && map[0][0]<='9') {
				dfs(0,0,3, map[0][0]-'0');
			}
			else {
				dfs(0,0,3,0);
			}
			if (isStop) System.out.println("YES");
			else System.out.println("NO");
		}
	}
	
	static void dfs(int y, int x, int d, int mem) {
		if (map[y][x] == '@') {
			isStop = true;
			if (isStop) return;
		}
		
		if (visited[y][x][d][mem] == true) return;
		visited[y][x][d][mem] = true;
		
		if (map[y][x] == '?') {
			for (int rand=0; rand<4; rand++) {
				int ny = y+dy[rand];
				int nx = x+dx[rand];
				if (ny<0) ny = R-1;
				else if (ny>=R) ny=0;
				else if (nx<0) nx=C-1;
				else if (nx>=C) nx=0;
				if (visited[ny][nx][rand][mem] == true) continue;
				
				dfs(ny, nx, rand, mem);
				visited[y][x][d][mem] = false;
				if (isStop) return;
			}
		} else {
			if (map[y][x] == '^') d=0;
			else if (map[y][x] == 'v') d=1;
			else if (map[y][x] == '<') d=2;
			else if (map[y][x] == '>') d=3;
			else if (map[y][x] == '_') {
				if (mem == 0) d=3;
				else d=2;
			}
			else if (map[y][x] == '|') {
				if (mem == 0) d=1;
				else d=0;
			}
			else if (map[y][x]>='0' && map[y][x]<='9') {
				mem = map[y][x]-'0';
			}
			else if (map[y][x] == '+') {
				if (mem==15) mem=0;
				else mem++;
			}
			else if (map[y][x] == '-') {
				if (mem==0) mem=15;
				else mem--;
			}
			int ny = y+dy[d];
			int nx = x+dx[d];
			if (ny<0) ny = R-1;
			else if (ny>=R) ny=0;
			else if (nx<0) nx=C-1;
			else if (nx>=C) nx=0;

			dfs(ny, nx, d, mem);
			if (isStop) return;
			
		}
	}
}

4. 사담

거의 4시간을 쓴 것 같은데 결국 친구의 도움을 받았다

틀린 이유를 발견하는 것도 한참 걸리고 테스트케이스를 분석하는 힘이 정말 정말 부족한 것 같다

나도 알고리즘 잘풀고싶다..

자고 일어나서 DFS로 다시풀어보자

 

이틀이 지나서 DFS로 풀어보았다.

문제 풀이를 까먹었다가 다시 풀어보니까 풀린다. 이 문제 처음봤을 땐 DFS로 접근했다가 시간초과로 터지길래 BFS로 바꿨었다. 그래서 DFS 풀이에 대한 아쉬움이 있었는데 결국 풀어서 속이 시원하다. 이번엔 방향전환을 수학 말고 BFS로 풀어보자..