[백준] 1987. 알파벳

---

풀이

모든 경우의 수를 DFS로 탐색하며 이전에 방문한 알파벳인 경우 가지치기를 진행하엿다. 이 때 이전 방문 노드를 확인하는 방법으로 초기에는 ArrayList를 사용했지만 시간초과가 발생하였고 이에 대한 이유가 ArrayList의 remove 과정에서 O(N)의 시간복잡도가 발생했기 때문이라고 판단하였다. 그래서 이전 방문 알파벳을 유지하는 방식을 StringBuilder를 사용하였고 마지막 인덱스를 삭제함으로써 시간 초과를 해결하였다.

하지만 이 방법도 너무 느려서 이를 확인하는 방법으로 비트마스킹을 사용하였고 모든 경우에 distance를 비교하는 것이 아니라 유망하지 않은 경우에만 distance를 비교하도록 개선하였다. 비트마스킹으로는 현재 알파벳 - 'A'를 해줌으로써 포함 여부를 확인하였다.

ArrayList

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

public class Solution1987 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int R, C, maxDistance = Integer.MIN_VALUE;
	static String[][] map;
	static boolean[][] check;
	static ArrayList<String> previous;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws IOException {
		String[] input = br.readLine().split(" ");
		R = Integer.parseInt(input[0]);
		C = Integer.parseInt(input[1]);
		map = new String[R][C];
		check = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			char[] line = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = String.valueOf(line[j]);
			}
		}

		previous = new ArrayList<String>();
		traversal(0, 0, 1);
		System.out.println(maxDistance);
	}

	private static void traversal(int x, int y, int distance) {
		maxDistance = Math.max(maxDistance, distance);
		check[x][y] = true;
		previous.add(map[x][y]);
		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i], nextY = y + dy[i];
			if (!isValid(nextX, nextY))
				continue;
			traversal(nextX, nextY, distance + 1);
		}
		
		previous.remove(map[x][y]);
		check[x][y] = false;
	}

	static boolean isValid(int x, int y) {
		if (x < 0 || y < 0 || x >= R || y >= C || previous.contains(map[x][y]) || check[x][y])
			return false;
		return true;
	}
}

StringBuilder

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int R, C, maxDistance = Integer.MIN_VALUE;
	static String[][] map;
	static boolean[][] check;
	static StringBuilder previous;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws IOException {
		String[] input = br.readLine().split(" ");
		R = Integer.parseInt(input[0]);
		C = Integer.parseInt(input[1]);
		map = new String[R][C];
		check = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			char[] line = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = String.valueOf(line[j]);
			}
		}

		previous = new StringBuilder(String.valueOf(map[0][0]));
		traversal(0, 0, 1);
		System.out.println(maxDistance);
	}

	private static void traversal(int x, int y, int distance) {
		maxDistance = Math.max(maxDistance, distance);

		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i], nextY = y + dy[i];
			if (!isValid(nextX, nextY))
				continue;
			check[nextX][nextY] = true;
			previous.append(map[nextX][nextY]);
			traversal(nextX, nextY, distance + 1);
			check[nextX][nextY] = false;
			previous = previous.deleteCharAt(previous.length()-1);
		}
	}

	static boolean isValid(int x, int y) {
		if (x < 0 || y < 0 || x >= R || y >= C || previous.toString().contains(map[x][y])
				|| check[x][y])
			return false;
		return true;
	}
}

Bitmasking

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

public class Solution {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int R, C, maxDistance = Integer.MIN_VALUE;
	static char[][] map;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws IOException {
		String[] input = br.readLine().split(" ");
		R = Integer.parseInt(input[0]);
		C = Integer.parseInt(input[1]);
		map = new char[R][C];

		for (int i = 0; i < R; i++) {
			char[] line = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = line[j];
			}
		}
		int start = map[0][0] - 'A';
		traversal(0, 0, 1, 0|1<<start);
		System.out.println(maxDistance);
	}

	private static void traversal(int x, int y, int distance, int flag) {
		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i], nextY = y + dy[i];
			if (!isValid(nextX, nextY, flag)) {
				maxDistance = Math.max(maxDistance, distance);
				continue;
			}
			int bit = map[nextX][nextY] - 'A';
			traversal(nextX, nextY, distance + 1, flag|1<<bit);
		}
	}

	static boolean isValid(int x, int y, int flag) {
		if (x < 0 || y < 0 || x >= R || y >= C )
			return false;
		
		int bit = map[x][y] - 'A';
		if ((flag&1<<bit) != 0) 
			return false;
		return true;
	}
}