[골드 1] 달이 차오른다, 가자.

https://www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

처음에 dfs로 잘못 접근함 돌아올 수가 없음

원숭이, 벽 부수기랑 비슷한 문제

bfs인데 큐에 들어가는 Data class가 다른 경우 같은 지점이라고 해도 가진 key값이 최초이면 queue에 넣어줘야 함

문제점

1. 문제 똑바로 안 읽어서 key를 사용하면 사라지는 줄 암

2. visited의 자료형을 뭘 쓸지 엄청 오래 고민함

 

참조 객체는 객체를 그대로 넣으면 다른 시뮬레이션에서 사용할 시 값이 바뀌므로 항상 깊은 복사를 해야 함에 주의

 

boolean [] have_keys로 선언하느라 다른 사람들 보다 시간 더 걸림

다른 사람들은 ex) 101010 2진 기법으로 키를 어떻게 가지고 있는지 기억함

 

내 방법이 좀 더 포괄적인 방법이지 않나?

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

class Data {
	int y, x;
	boolean[] have_keys;
	int depth;

	Data(int y, int x, boolean[] have_keys, int depth) {
		this.y = y;
		this.x = x;
		this.have_keys = have_keys;
		this.depth = depth;
	}
}

public class Main {

	public static int[] DY = new int[] { 1, -1, 0, 0 };
	public static int[] DX = new int[] { 0, 0, 1, -1 };
	public static char[] KEYS = new char[] { 'a', 'b', 'c', 'd', 'e', 'f' };
	public static char[] DOORS = new char[] { 'A', 'B', 'C', 'D', 'E', 'F' };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int N, M;
		char[][] arr;

		////////////////////////////////////////////////////////////////

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new char[N][M];

		for (int i = 0; i < arr.length; i++) {
			String input_line = br.readLine();
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = input_line.charAt(j);
			}
		}

		///////////////////////////////////////////////////////////////

		Queue<Data> queue = new LinkedList<>();

		// 시작 지점 찾기
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				if (arr[i][j] == '0') {
					queue.add(new Data(i, j, new boolean[6], 0));
				}
			}
		}

		ArrayList<ArrayList<boolean[]>> big_arrayList = new ArrayList<>();
		for (int i = 0; i < N * M; i++)
			big_arrayList.add(new ArrayList<boolean[]>());

		big_arrayList.get(queue.peek().y * M + queue.peek().x).add(new boolean[6]);

		while (!queue.isEmpty()) {
			Data tmp = queue.remove();
			
//			System.out.println(" y = " + tmp.y + " x = " + tmp.x);
//			System.out.println(tmp.have_keys[0] + " " + tmp.have_keys[1] + " " + tmp.have_keys[2] + " " + tmp.have_keys[3] +" " + tmp.have_keys[4] + " " + tmp.have_keys[5]);

			if (arr[tmp.y][tmp.x] == '1') {
				sb.append(tmp.depth);
				break;
			}

			for (int d = 0; d < 4; d++) {
				int new_y = tmp.y + DY[d];
				int new_x = tmp.x + DX[d];
				boolean[] new_have_keys = new boolean[6];
				for (int i = 0; i < 6; i++) {
					new_have_keys[i] = tmp.have_keys[i];
				}

				if (new_y >= 0 && new_x >= 0 && new_y < arr.length && new_x < arr[0].length) {

					boolean can = true;

					if (arr[new_y][new_x] == '#')
						can = false;
					for (int i = 0; i < 6; i++) {
						if (arr[new_y][new_x] == KEYS[i]) {
							new_have_keys[i] = true;
						}
						if (arr[new_y][new_x] == DOORS[i]) {
							if (!new_have_keys[i])
								can = false;
						}
					}
					if (can) {
						boolean find_same = false;
						for (int i = 0; i < big_arrayList.get(new_y * M + new_x).size(); i++) {
							boolean find_same_sub = true;
							for (int j = 0; j < 6; j++) {
								if (new_have_keys[j] != big_arrayList.get(new_y * M + new_x).get(i)[j]) {
									find_same_sub = false;
								}
							}
							if (find_same_sub)
								find_same = true;
						}

						if (!find_same) {
							big_arrayList.get(new_y * M + new_x).add(new_have_keys);
							queue.add(new Data(new_y, new_x, new_have_keys, tmp.depth + 1));
						}

					}
				}
			}
		}

		if (sb.length() == 0)
			sb.append("-1");

		System.out.println(sb);

	}
}