🔸 문제 간략하게 살펴보기

 빈 칸('.') - 언제나 이동할 수 있다.

 벽 ('#')  - 절대 이동할 수 없다.

 열쇠 ('a', 'b', 'c', 'd', 'e', 'f')  -언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다.
 문 ('A', 'B', 'C', 'D', 'E', 'F') - 대응하는 열쇠가 있을 때만 이동할 수 있다.

 민식이의 현재 위치 ('0')  - 빈 곳이고, 민식이가 현재 서 있는 곳이다. 

 출구 ('1') - 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. 

 * 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다.

'0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.

=> 미로를 탈출하는데 걸리는 이동횟수의 최솟값

🔸포인트 

- 미로를 탈출하는데 걸리는 이동횟수의 최솟값 => bfs 

- 방문한 곳 체크 처리, 열쇠 처리, 문 처리

🔸방문한 곳 처리

처음엔 2차원 boolean 형으로 방문 여부 처리를 하려다가 이 문제 같은 경우 왔던 길을 재 방문하는 경우가 있기때문에 방문처리에 대해 잘 생각해야 한다.

그렇다고 방문처리를 안한다면 방문했던 부분을 다시 방문할 수도 있으니 방문처리를 해야한다.

boolean 형 visited [가로][세로][열쇠의 조합] 3차원을 이용해서 처리

-> 열쇠의 조합 : *비트마스킹 이용

🙋 열쇠 조합을 넣는 이유 ? 

-> 여러 개의 열쇠를 가지고 있을 수 있음

이를 쉽게 핸드링하기 위해 | , & 을 가지고 열쇠 추가, 대응하는 열쇠와 문을 손쉽게 찾을 수 있다.

열쇠 ('a', 'b', 'c', 'd', 'e', 'f') 0~ 63 조합 => 총 64종류 

열쇠 조합 순서

'f','e','d','c','b','a'

(1) 열쇠 a일 경우

=> 0 0 0 0 0 1 

(2) 열쇠 d 일 경우

=> 0 0 1 0 0 0

(1) | (2) 의 결과 = 열쇠 d,a 일 경우

=> 0 0 1  0 0 1

// 만약 열쇠면 ? 열쇠면 민식이 주머니에 넣기 ** 언제나 이동가능
					if (map[nx][ny] == 'a' || map[nx][ny] == 'b' || map[nx][ny] == 'c' || map[nx][ny] == 'd'
							|| map[nx][ny] == 'e' || map[nx][ny] == 'f') {
						// 비트마스킹
						int nkey = 1 << (map[nx][ny] - 'a');
						nkey = temp.key | nkey;
						if (!visited[nx][ny][nkey]) {
//							System.out.println("열쇠 획득");
							visited[nx][ny][nkey] = true; // 방문 체크하고
							que.offer(new Minsic(nx, ny, temp.cnt + 1, nkey)); // 이동해보쟈
						}

					}

대응하는 문을 찾을 경우 

(1) 문 A일 경우

=> 0 0 0 0 0 1

(2) 가지고 있는 열쇠 d,a인 경우 

=> 0 0 1 0 0 1

(1) & (2) 의 결과  

=> 0 0 0 0 0 1

(1) & (2) 의 결과가 0 보다 크다면 대응하는 열쇠를 가지고 있다

// 만약 문의 경우 ; 대응하는 열쇠가 있는 경우에만 이동할 수 있고, 대응하는 열쇠가 없는 경우 이동하지 못한다.
					else if (map[nx][ny] == 'A' || map[nx][ny] == 'B' || map[nx][ny] == 'C' || map[nx][ny] == 'D'
							|| map[nx][ny] == 'E' || map[nx][ny] == 'F') {

						int ndoor = 1 << (map[nx][ny] - 'A');

						// 열쇠랑 문이 짝꿍일때
						if ((temp.key & ndoor) > 0) {
							// 이동해보쟈
							if (!visited[nx][ny][temp.key]) {
//								System.out.println("문 열고 이동");
								visited[nx][ny][temp.key] = true;
								que.offer(new Minsic(nx, ny, temp.cnt + 1, temp.key));
							}
						} else {
//							System.out.println("문 못열어 이동 불가");
							continue;
							// 이동불가능
						}

열쇠와 문을 방문할 경우와 그렇지 않은 경우로 나눠 이동하기 

// 만약 열쇠면 ? 열쇠면 민식이 주머니에 넣기 ** 언제나 이동가능
					if (map[nx][ny] == 'a' || map[nx][ny] == 'b' || map[nx][ny] == 'c' || map[nx][ny] == 'd'
							|| map[nx][ny] == 'e' || map[nx][ny] == 'f') {
						// 비트마스킹
						int nkey = 1 << (map[nx][ny] - 'a');
						nkey = temp.key | nkey;
						if (!visited[nx][ny][nkey]) {
//							System.out.println("열쇠 획득");
							visited[nx][ny][nkey] = true; // 방문 체크하고
							que.offer(new Minsic(nx, ny, temp.cnt + 1, nkey)); // 이동해보쟈
						}

					} // 만약 문의 경우 ; 대응하는 열쇠가 있는 경우에만 이동할 수 있고, 대응하는 열쇠가 없는 경우 이동하지 못한다.
					else if (map[nx][ny] == 'A' || map[nx][ny] == 'B' || map[nx][ny] == 'C' || map[nx][ny] == 'D'
							|| map[nx][ny] == 'E' || map[nx][ny] == 'F') {

						int ndoor = 1 << (map[nx][ny] - 'A');

						// 열쇠랑 문이 짝꿍일때
						if ((temp.key & ndoor) > 0) {
							// 이동해보쟈
							if (!visited[nx][ny][temp.key]) {
//								System.out.println("문 열고 이동");
								visited[nx][ny][temp.key] = true;
								que.offer(new Minsic(nx, ny, temp.cnt + 1, temp.key));
							}
						} else {
//							System.out.println("문 못열어 이동 불가");
							continue;
							// 이동불가능
						}

					} else {
						if (!visited[nx][ny][temp.key]) {
//							System.out.println("이동");
							visited[nx][ny][temp.key] = true;
							que.offer(new Minsic(nx, ny, temp.cnt + 1, temp.key));
						}
					}

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };

	static class Minsic {
		int x, y, cnt;
		// 열쇠 꾸러미들 관리
		int key;

		public Minsic(int x, int y, int cnt, int key) {
			super();
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.key = key;
		}

		@Override
		public String toString() {
			return "Minsic [x=" + x + ", y=" + y + ", cnt=" + cnt + ", key=" + key + "]";
		}

	}

	static int N, M;
	static char[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken()); // 세로크기
		M = Integer.parseInt(st.nextToken()); // 가로크기

		map = new char[N][M];
		Minsic start = null;
		for (int i = 0; i < N; i++) { // ->
			String str = br.readLine();
			for (int j = 0; j < M; j++) { // ↓
				map[i][j] = str.charAt(j);
				if (map[i][j] == '0') {
					start = new Minsic(i, j, 0, 0);
				}

			}
		}

		/* 출력 확인용 */
//		for(int i=0;i<N;i++) {
//			for(int j=0;j<M;j++) {
//				System.out.print(map[i][j]+" ");
//			}
//			System.out.println();
//		}
		
		/* 민식이 처음 위치 확잉 */
//		System.out.println(start.toString());
		visited = new boolean[N][M][64];
		int result = bfs(start.x, start.y, start.cnt, start.key);
		System.out.println(result);

	}

	// [x][y][열쇠 조합]
	static boolean[][][] visited;

	// x=Minsic.x y= Minsic.y
	static int bfs(int x, int y, int cnt, int key) {
		Queue<Minsic> que = new ArrayDeque<>();
		// 처음 위치 집어 넣고
		que.offer(new Minsic(x, y, cnt, key));
		visited[x][y][key] = true;
		
		while (!que.isEmpty()) {
			Minsic temp = que.poll();

			// 탈출해보자
			if (map[temp.x][temp.y] == '1') {
				return temp.cnt;
			}

			// 민식이가 갈 수 있는 곳으로 사방탐색을 해보쟈
			for (int d = 0; d < 4; d++) {
				int nx = temp.x + dx[d];
				int ny = temp.y + dy[d];

				if (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] != '#') {

//					System.out.println("nx : " + nx + " , ny : " + ny + " , temp.cnt :" + temp.cnt+" ,temp.key :"+temp.key);
					
					
					// 만약 열쇠면 ? 열쇠면 민식이 주머니에 넣기 ** 언제나 이동가능
					if (map[nx][ny] == 'a' || map[nx][ny] == 'b' || map[nx][ny] == 'c' || map[nx][ny] == 'd'
							|| map[nx][ny] == 'e' || map[nx][ny] == 'f') {
						// 비트마스킹
						int nkey = 1 << (map[nx][ny] - 'a');
						nkey = temp.key | nkey;
						if (!visited[nx][ny][nkey]) {
//							System.out.println("열쇠 획득");
							visited[nx][ny][nkey] = true; // 방문 체크하고
							que.offer(new Minsic(nx, ny, temp.cnt + 1, nkey)); // 이동해보쟈
						}

					} // 만약 문의 경우 ; 대응하는 열쇠가 있는 경우에만 이동할 수 있고, 대응하는 열쇠가 없는 경우 이동하지 못한다.
					else if (map[nx][ny] == 'A' || map[nx][ny] == 'B' || map[nx][ny] == 'C' || map[nx][ny] == 'D'
							|| map[nx][ny] == 'E' || map[nx][ny] == 'F') {

						int ndoor = 1 << (map[nx][ny] - 'A');

						// 열쇠랑 문이 짝꿍일때
						if ((temp.key & ndoor) > 0) {
							// 이동해보쟈
							if (!visited[nx][ny][temp.key]) {
//								System.out.println("문 열고 이동");
								visited[nx][ny][temp.key] = true;
								que.offer(new Minsic(nx, ny, temp.cnt + 1, temp.key));
							}
						} else {
//							System.out.println("문 못열어 이동 불가");
							continue;
							// 이동불가능
						}

					} else {
						if (!visited[nx][ny][temp.key]) {
//							System.out.println("이동");
							visited[nx][ny][temp.key] = true;
							que.offer(new Minsic(nx, ny, temp.cnt + 1, temp.key));
						}
					}
				}
			}

		}

		return -1;

	}

}

비트마스킹 개념 참고

📮개인 공부를 위한 공간으로 틀린 부분이 있을 수도 있습니다.📮

문제점 및 수정 사항이 있을 시, 언제든지 댓글로 피드백 주시기 바랍니다.

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int num[] = new int[9];
		
		for(int i=0;i<num.length;i++) {
			num[i]= scanner.nextInt();
		}
        	int count = 0;
		int max = 0;
        
		for(int i=0;i<num.length;i++) {
			if (num[i]>max) {
				max = num[i];
		      		count =i+1;
			}
			
		}
		
		System.out.println(max);
		System.out.println(count);
	}
	
}

Arrays.binarysearch() 

🙋 질문  ➜ 🙆

🙋: 어느 부분에서 오류가 나는지 이클립스에선 오류없이 잘 돌아가는데 백준에서 제출시 자꾸 실패로 뜬다.

🙆: int max = num[0] ➜ int max = 0 으로 바꾸고 제출하니 성공

📮개인 공부를 위한 공간으로 틀린 부분이 있을 수도 있습니다.📮

문제점 및 수정 사항이 있을 시, 언제든지 댓글로 피드백 주시기 바랍니다.