[Java] 백준 1987 알파벳

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

난이도

골드4

문제

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

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

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

입력

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

출력

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

내 코드

같은 문제임에도 시간이 대략 3배정도 차이가 날 수 있다... 가장 먼저 생각난 방식부터 효율적으로 구현하는 방식까지 생각해봤고, 총 4번의 제출을 했다.

제출1

방문한 알파벳 set으로 저장 -> 1872ms

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

class Main {

	static int R, C, ans;
	static char[][] map;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -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][C];

		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		}

		ans = 0;
		HashSet<Character> set = new HashSet<>();
		set.add(map[0][0]);
		dfs(new int[] { 0, 0 }, set);

		System.out.println(ans);
	}

	public static void dfs(int[] now, HashSet<Character> set) {
		ans = Math.max(ans, set.size());
		if(ans == 26) {
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = now[0] + dx[i];
			int ny = now[1] + dy[i];
			if (0 > nx || nx >= R || 0 > ny || ny >= C) {
				continue;
			}
			if (set.contains(map[nx][ny])) {
				continue;
			}
			set.add(map[nx][ny]);
			dfs(new int[] { nx, ny }, set);
			set.remove(map[nx][ny]);
		}
	}
}

제출2

2차원 배열로 방문 확인, 알파벳 방문 처리는 int로 변환하고 boolean으로 저장 -> 1136ms

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

class Main {

	static int R, C, ans;
	static char[][] map;
	static boolean[][] visited;
	static boolean[] alpha;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -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][C];
		visited = new boolean[R][C];
		alpha = new boolean[26];

		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		}

		ans = 0;
		visited[0][0] = true;
		alpha[map[0][0] - 'A'] = true;
		dfs(0, 0, 1);
		System.out.println(ans);
	}

	public static void dfs(int x, int y, int depth) {
		ans = Math.max(ans, depth);
		
		if(depth == 26) {
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 > nx || nx >= R || 0 > ny || ny >= C) {
				continue;
			}
			
			int next = map[nx][ny] - 'A';
			if (!visited[nx][ny] && !alpha[next]) {
				visited[nx][ny] = true;
				alpha[next] = true;
				
				dfs(nx, ny, depth+1);
				
				visited[nx][ny] = false;
				alpha[next] = false;
			}
		}
	}
}

제출3

생각해보니 굳이 2차원 배열로 방문처리할 필요가 없어서 알파벳 방문처리만 시도 -> 900ms

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

class Main {

	static int R, C, ans;
	static char[][] map;
	static boolean[] alpha;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -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][C];
		alpha = new boolean[26];

		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		}

		ans = 0;
		alpha[map[0][0] - 'A'] = true;
		dfs(0, 0, 1);
		System.out.println(ans);
	}

	public static void dfs(int x, int y, int depth) {
		ans = Math.max(ans, depth);
		
		if(depth == 26) {
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 > nx || nx >= R || 0 > ny || ny >= C) {
				continue;
			}
			
			int next = map[nx][ny] - 'A';
			if (!alpha[next]) {
				alpha[next] = true;
				dfs(nx, ny, depth+1);
				alpha[next] = false;
			}
		}
	}
}

제출4

비트마스킹 -> 692ms

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

class Main {

    static int R, C, ans;
    static char[][] map;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -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][C];

        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j);
            }
        }

        ans = 0;
        dfs(0, 0, 1 << (map[0][0] - 'A'), 1);
        System.out.println(ans);
    }

    public static void dfs(int x, int y, int visited, int depth) {
        ans = Math.max(ans, depth);

        if (ans == 26) {
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
                continue;
            }

            int nextChar = map[nx][ny] - 'A';
            if ((visited & (1 << nextChar)) == 0) {
                dfs(nx, ny, visited | (1 << nextChar), depth + 1);
            }
        }
    }
}