backjoon 1987 : 알파벳 / java

www.acmicpc.net/problem/1987

1987번: 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

풀이

dfs로 탐색하면서 다시 되돌아오는 부분에 애를 먹었다.. 아직 익숙하지 않은 것 같다 ㅠㅠ 흑흑

 

1. dfs 탐색하면서 한 칸씩 전진 하면서 방문 체크

2. dfs 탐색을 더이상 못할 때 distance 갱신하고 돌아오면서 방문한 곳 체크 해제

1. 보통 dfs

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

public class Main {	
	static int R, C;
	static int answer = Integer.MIN_VALUE;
	static boolean[] alphabet;
	static char map[][];
//	                                   상 하 좌 우
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R + 1][C + 1];
			
		for(int i = 1; i <= R; i++) {
			String str = br.readLine();
			for(int j = 1; j <= C; j++) {
				map[i][j] = str.charAt(j - 1);
			}
		}
		
		alphabet = new boolean[26];
		alphabet[map[1][1] - 'A'] = true;
		dfs(1, 1, alphabet, 1);
		System.out.println(answer);
	}
	
	static void dfs(int x, int y, boolean[] alpha, int cnt) {	
		for(int i = 0; i < 4; i++) {		
			int mx = x + dx[i];
			int my = y + dy[i];
			
			if(mx > R || my > C || mx < 1 || my < 1) continue;
			if(alpha[map[mx][my] - 'A']) {
				answer = Math.max(cnt, answer);
				continue;
			}
			
			alpha[map[mx][my] - 'A'] = true;
			dfs(mx, my, alpha, cnt + 1);
			alpha[map[mx][my] - 'A'] = false;				
		}
	}
}

2. bit masking

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

public class Main {	
	static int R, C;
	static int answer = Integer.MIN_VALUE;
	static char[][] map;
	static int[][] visited;
//	                                   상 하 좌 우
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R + 1][C + 1];
		visited = new int[R + 1][C + 1];
			
		for(int i = 1; i <= R; i++) {
			String str = br.readLine();
			for(int j = 1; j <= C; j++) {
				map[i][j] = str.charAt(j - 1);
			}
		}
		dfs(1, 1, 1 << map[1][1] - 'A', 1);
		System.out.println(answer);
	}
	
	static void dfs(int x, int y, int bit, int cnt) {	
		if(visited[x][y] == bit) return;
		visited[x][y] = bit;
		answer = Math.max(cnt, answer);
		
		for(int i = 0; i < 4; i++) {		
			int mx = x + dx[i];
			int my = y + dy[i];
			
			if(mx > R || my > C || mx < 1 || my < 1) continue;
			if((bit & 1 << map[mx][my] - 'A') != 0) continue;
			dfs(mx, my, bit | 1 << map[mx][my] - 'A', cnt + 1);			
		}
	}
}

34, 35번째줄을 지워도 제대로 동작은 합니다!

이미 같은 경로로 진행했을 때 그 부분을 pass합니다