[백준]_18188 다오의 데이트

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class B18188 {
	static int H, W, N;
	static char[][] arr;
	static char[][] command;
	static int[][] delta = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
	static int[] d;
	static boolean flag, ans;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		
		arr = new char[H][W];
		for (int i = 0; i < H; i++) {
			arr[i] = br.readLine().toCharArray();
			for (int j = 0; j < W; j++) {
				if (arr[i][j] == 'D') {
					d = new int[] {i,j};
				}
			}
		}
		
		N = Integer.parseInt(br.readLine());
		command = new char[N][2];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			command[i][0] = st.nextToken().charAt(0);
			command[i][1] = st.nextToken().charAt(0);
		}
		
		dfs(0,d[0],d[1], new ArrayList<>());
		// key를 저장하기 위한 list
		System.out.println(ans?sb:"NO");
	}

	private static void dfs(int start, int r, int c, List<Character> list) {
		for (int i = start; i < N; i++) {
			flag = false;
			for (int j = 0; j < 2; j++) {
				int dir = keydir(command[i][j]);
				int x = r + delta[dir][0];
				int y = c + delta[dir][1];

				if (inside(x, y) && arr[x][y] != '@') {
					list.add(command[i][j]);
					flag = true;
					// 찾을 경우 바로 결과 출력, ans를 이용해 모두 종료
					if (arr[x][y] == 'Z') {
						sb.append("YES").append("\n");
						for (int k = 0; k < list.size(); k++) {
							sb.append(list.get(k));
						}
						ans = true;
						return;
					} else {
						// 다음꺼 탐색
						dfs(i + 1, x, y, list);
						if(ans) return;
						list.remove(list.size() - 1);
						flag = false;
					}
				}
				if(ans) return;
			}
			// 끝까지 탐색했는데 찾지 못함
			if(!flag) return;
		}
	}

	// 입력받은 키를 index로 변환
	private static int keydir(char c) {
		int result = 0;
		if (c == 'W') {
			result = 0;
		} else if (c == 'A') {
			result = 1;
		} else if (c == 'S') {
			result = 2;
		} else if (c == 'D') {
			result = 3;
		}
		return result;
	}

	public static boolean inside(int x, int y) {
		return x >= 0 && y >= 0 && x < H && y < W;
	}
}