[Java] 백준 1194번 달이 차오른다, 가자. 문제 952hi의 접근방법

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

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

---

1. 접근방법

 

길 찾기 문제는 bfs라는 공식을 매번 기억하고 있었는데 왠지 dfs로 재귀를 타고 싶었다.

dfs나 bfs 문제 둘다 중복방문 처리가 핵심이라고 생각했다. 

 

처음 문제를 읽고 알파벳 a~z 모두 등장한다고 생각해서 알파뱃 개수인 26개 배열과 키의 개수를 가지고 재귀를 돌리면서 매번 4방탐색을 해준다면 가뿐하다고 생각했다. 그런데 시간초과를 발생했다.

50 * 50 행렬을 재귀를 타면 4의 50이라 터진 것 같았다.

 

dfs가 안되면 bfs도 안되지않을까라는 생각이 있었는데 일단은 해보자고 생각했다.

시간초과를 받고 문제를 다시읽어보니 a~f였기때문에 비트마스킹을 사용할 수 있다고 생각했다.

a~z면 2의 26이라 쓰기 힘들어서 배열을 넣고 돌렸는데 a~f면 2의 6승만으로 방문처리가 가능해서 이득이기 때문이다.

 

dfs과 코드 자체는 다른 부분없지만 문제는 맞았다. 

 

왜 dfs는 안돼고 bfs는 안돼는지 궁금하다...

 

2. 실수

 

비트 마스킹 부분 에서 알파벳 6개니까 65개만큼 배열크기를 잡아줘야하는데 f가 5번째 비트니 33개로 준게 문제를 발생시켜서 이부분 실수가 있었다.

 

3. 느낀점

 

bfs dfs 문제마다 뭘 적용해야할지 알아내는 노하우가 필요 할것 같다.

 

4. 코드1~2 

dfs 오답코드 정답은 잘나온다

 

import java.io.*;
import java.util.*;
public class Main {
	static int row,col,cnt,temp[][];
	static char[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		row = Integer.parseInt(stz.nextToken());
		col = Integer.parseInt(stz.nextToken());
		temp = new int[row][col];
		map = new char[row][col];
		cnt = Integer.MAX_VALUE;
		
		for(int i=0;i<row;i++) {
			Arrays.fill(temp[i], -1);
			map[i] = br.readLine().toCharArray();
		}
		// 사이즈 1일때 예외처리
		if(row==0 && col==0) {
			System.out.println(0);
		}else {
		out:for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					if(map[i][j]=='0') {
						temp[i][j] = 0;
						map[i][j]='.';
						moon(i,j,0,new boolean[26],0);
						break out;
					}
				}
			}
		}
		if(cnt==Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(cnt);
	}
	static int[][] dxdy = { { 0, 0, 1, -1 }, { 1, -1, 0, 0 } };
	private static void moon(int x, int y,int move,boolean[] key,int keyval) {
		//이미 커져버린경우 컷
		if(move>cnt) return;
		// 탈출하는 경우 갱신
		if(map[x][y]=='1') {
			cnt = Math.min(cnt, move);
			return;
		}
		int nx,ny,comp;
		for(int i=0;i<4;i++) {
			nx = x+dxdy[0][i];
			ny = y+dxdy[1][i];
			// 범위 및 벽 처리
			if(0<=nx && nx<row && 0<=ny && ny<col && map[nx][ny]!='#' && move<cnt) {
				// 대문자 처리
				if(map[nx][ny]-0>=65 && map[nx][ny]-0<97) {
					if(!key[map[nx][ny]-'A']) continue;
				}
				// 중복방문 제외
				if(temp[nx][ny]<keyval) {
					comp = temp[nx][ny];
					temp[nx][ny] = keyval;
					
					//소문자 처리 A~Z 확인
					if(map[nx][ny]-0>=97 && map[nx][ny]-0<=122) {
						if(!key[map[nx][ny]-'a']) {
							keyval += 1;
							key[map[nx][ny]-'a'] = true;
							moon(nx,ny,move+1,key,keyval);
							keyval -= 1;
							key[map[nx][ny]-'a'] = false;
						}
					}else moon(nx,ny,move+1,key,keyval);
					temp[nx][ny] = comp;
				}
			}
		}
	}
}

bfs 정답코드

 

import java.io.*;
import java.util.*;
public class boj1194ver2 {
	static int row,col,movecnt;
	static char map[][];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		
		row = Integer.parseInt(stz.nextToken());
		col = Integer.parseInt(stz.nextToken());
		movecnt = Integer.MAX_VALUE;
		map = new char[row][col];
		
		for(int i=0;i<row;i++)map[i] = br.readLine().toCharArray();
		if(row == 1 && col == 1) System.out.println(0);
		else {
		out:for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					if(map[i][j]=='0') {
						bfs(i,j);
						if(movecnt==Integer.MAX_VALUE) System.out.println(-1);
						else System.out.println(movecnt);
						break out;
					}
				}
			}
		}
	}
	static int[][] dxdy = { { 0, 0, 1, -1 }, { 1, -1, 0, 0 } };
	private static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] {x,y,0,0});//0 : x 1: y 2: bit 3:move
		boolean visited[][][] = new boolean[row][col][65];
		visited[x][y][0] = true;
		
		int[] comp;
		int nx,ny,check;
		while(!q.isEmpty()) {
			comp = q.poll();
			if(map[comp[0]][comp[1]]=='1') {
				movecnt = Math.min(movecnt, comp[3]);
			}
			for(int i=0;i<4;i++) {
				nx = comp[0] + dxdy[0][i];
				ny = comp[1] + dxdy[1][i];
				// 범위 안이고 벽이 아니지?
				if(0<=nx && nx<row  && 0<=ny && ny<col && map[nx][ny]!='#' && !visited[nx][ny][comp[2]]) {
					// 대문자 체크
					if(map[nx][ny]-0>=65 && map[nx][ny]-0<=70 && (comp[2]&1<<map[nx][ny]-'A')==0) continue;
					//소문자 체크
					if(map[nx][ny]-0>=97 && map[nx][ny]-0<=102) {
						if((comp[2]&1<<map[nx][ny]-'a')==0) {
							check = comp[2]|1<<map[nx][ny]-'a';
							q.offer(new int[] {nx,ny,check,comp[3]+1});
							visited[nx][ny][check] = true;
							continue;
						}
					}
					q.offer(new int[] {nx,ny,comp[2],comp[3]+1});
					visited[nx][ny][comp[2]]=true;
				}
			}
		}
	}
}