SWEA 1824 <혁진이의 프로그램 검증>

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

SW Expert Academy

 

DFS로 풀었지만 DFS를 사용하려면 많은 생각과 방문처리가 필요한 문제였다.

 

우선 기본적으로 알아야 할 것은 각각의 위치마다 0~15 값을 가진 총 4개 (위, 아래, 좌, 우) 방향을 가질 수 있다.

 

그러므로 일반적인 boolean 2차원 배열이 아닌 visit[x][y][값][방향] 이렇게 표시된 4차원 배열이 필요하다.

 

이 문제를 DFS를 풀게되면 스택오버플로우가 발생하는 경우가 가장 많을 것이다.

 

재귀의 횟수는 20(행)*20(열)*16(수)*4(방향) 으로 25600이다.

 

하지만 함수안에 내장된 메모리가 크기 때문에 스택 오버 플로우가 발생한다.

 

스택오버플로우가 발생하는 문제는 ?가 있는 자리에서 특별한 방문처리를 해주지 않았기 때문이다.

 

1
20 20
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
???????????????????+

 

이 코드에서 많은 재귀를 돌아 스택오버 플로우가 발생한다.

 

문제 풀이

1. 4차원 방문처리를 위한 visit[][][][] boolean배열을 선언한다.
2. 시작점인 dfs(0,0,1,0)  0, 0, 오른쪽, 현재 값로 시작을 한다.
3. @지점을 밟게되면 flag는 true 즉 탈출 가능 반복을 돈다면 return을 한다.
4. flag 값을 확인해서 결과를 출력한다.

이 문제의 핵심은 말 그대로?를 어떻게 처리해줄 것 인가였다.

 

그래서 나는 ?를 밟게 되면 그지점의 4방향을 방문 처리해주었다.

 

이외에는 모두 알고 있는 dfs와 같다.

 

bfs로 풀게 된다면 재귀를 돌지 않기 때문에 쉽게 풀릴 수 있는 문제였다.

 

전체 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution {

	static int t, r, c;
	static boolean visit[][][][], flag, can;
	static String map[];
	static int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for (int tc = 1; tc <= t; tc++) {
			st = new StringTokenizer(br.readLine());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			map = new String[r];
			visit = new boolean[r][c][4][16];
			flag = false;
			for (int i = 0; i < r; i++) {
				map[i] = br.readLine();

			}
			dfs(0, 0, 1, 0);// 무한 반복 조건은 현재위치를 값은값과 같은 방향을 가지고 방문한 기록이 있으면
			if (flag) {
				System.out.println("#" + tc + " YES");
			} else {
				System.out.println("#" + tc + " NO");
			}
		}
	}

	private static void dfs(int x, int y, int d, int sum) {
		// TODO Auto-generated method stub
		if(visit[x][y][d][sum])
			return;
		visit[x][y][d][sum]=true;
		if (map[x].charAt(y) == '?') {
			visit[x][y][0][sum]=true;
			visit[x][y][1][sum]=true;
			visit[x][y][2][sum]=true;
			visit[x][y][3][sum]=true;
			for (int di = 0; di < 4; di++) {
				d = di;
				int x1 = (x + dir[d][0] + r) % r;
				int y1 = (y + dir[d][1] + c) % c;
				
				dfs(x1, y1, d, sum);
				if (flag) {
					return;
				}
			}
		} else {
			if (map[x].charAt(y) == '<') {
				d = 3;
			} else if (map[x].charAt(y) == '>') {
				d = 1;
			} else if (map[x].charAt(y) == '^') {
				d = 0;
			} else if (map[x].charAt(y) == 'v') {
				d = 2;
			} else if (map[x].charAt(y) == '_') {
				if (sum == 0) {
					d = 1;
				} else {
					d = 3;
				}
			} else if (map[x].charAt(y) == '|') {
				if (sum == 0) {
					d = 2;
				} else {
					d = 0;
				}
			} else if (map[x].charAt(y) == '.') {

			} else if (map[x].charAt(y) == '@') {
				flag = true;
				return;
			} else if (map[x].charAt(y) >= '0' && map[x].charAt(y) <= '9') {
				sum = map[x].charAt(y) - '0';
			} else if (map[x].charAt(y) == '+') {
				sum++;
				if (sum > 15) {
					sum = 0;
				}
			} else if (map[x].charAt(y) == '-') {
				sum--;
				if (sum < 0) {
					sum = 15;
				}
			}
			int x1 = (x + dir[d][0] + r) % r;
			int y1 = (y + dir[d][1] + c) % c;
			dfs(x1, y1, d, sum);

		}
	}

}