백준 1987번
https://www.acmicpc.net/problem/1987

문제

---

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

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

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

생각하기

---

DFS를 통해서 2차원 배열을 탐색해가면서 방문한 알파벳여부를 검색하면 쉽게 풀 수 있다.

물론 다른 분들이 풀으신 코드는 역대급이었는데, 비트레이트 연산을 통해서 시간효율을 극대화 시켜서 풀었다.

나는 그정도 머리까지는 되지않기때문에 일반적인 방법을 통해서 문제를 풀고, 나중에 따로 다른 분들 풀이를 보고 따로 공부했다.

동작

핵심은 DFS만 알면된다.

		if(alp[arr[x][y]-65]) {
			result = Math.max(result, count);
			return;
		}
		else {
			alp[arr[x][y]-65] = true;

			for(int i=0; i<4; i++) {
				nowX = dirX[i] + x;
				nowY = dirY[i] + y;

				if( range_check() ) {
					DFS(nowX, nowY, count + 1);
				}
			}

			alp[arr[x][y] - 65] = false;
		}

DFS를 실행하면서 x와 y값을 매개변수로 받아오고, arr의 좌표에 -65를 하면 'A'의 아스키코드인 65에서 빼주므로 0을 구할 수 있다.

그러면 총 26개의 자리에서 대문자의 개수만큼 있는 alp배열을 방문여부처럼 사용해서 alp의 좌표값이 true일 경우, 해당 알파벳은 이미 방문했다는 것을 알 수 있다.

만약 방문한 알파벳일 경우, 더 이상 진행할 수 없으므로 return하여 result와 count중 큰 값으로 result를 갱신해준다.

만약 방문하지 않은 알파벳일 경우, 계속 갈 수 있는 방향을 탐색하면서 DFS재귀를 실행한다.

코드

---

Java

import java.util.*;
import java.io.*;

public class Main {
	static int dirX[] = {0, 0, -1, 1}; // 상 하 좌 우
	static int dirY[] = {-1, 1, 0, 0};
	static char arr[][]; 
	static boolean alp[] = new boolean[26];

	static int nowX, nowY;
	static int R, C;
	static int result = Integer.MIN_VALUE;

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

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		arr = new char[R][C];

		for(int i=0; i<R; i++) {
			String temp = br.readLine();

			for(int j=0; j<C; j++) {
				arr[i][j] = temp.charAt(j);
			}
		}

		DFS(0, 0, 0);
		System.out.println(result);

	} // End of main

	private static void DFS( int x, int y, int count) {

		if(alp[arr[x][y]-65]) {
			result = Math.max(result, count);
			return;
		}
		else {
			alp[arr[x][y]-65] = true;

			for(int i=0; i<4; i++) {
				nowX = dirX[i] + x;
				nowY = dirY[i] + y;

				if( range_check() ) {
					DFS(nowX, nowY, count + 1);
				}
			}

			alp[arr[x][y] - 65] = false;
		}

	} // End of DFS

	private static boolean range_check() {
		return (nowX >= 0 && nowX < R && nowY >= 0 && nowY < C);
	} // End of range_check
	
} // End of Main class

Kotlin

import java.util.*;
import java.io.*;

private val dirX = arrayOf(0, 0, -1, 1) // 상 하 좌 우
private val dirY = arrayOf(-1, 1, 0, 0) // 상 하 좌 우
private lateinit var arr : Array<Array<Char>>
private lateinit var alp : Array<Array<Int>>
private var R = 0;
private var C = 0;
private var nowX = 0; private var nowY = 0;
private var result = Int.MIN_VALUE;

fun main() {
    var br = BufferedReader( InputStreamReader(System.`in`) )
    var st = StringTokenizer(br.readLine())

    R= st.nextToken().toInt()
    C = st.nextToken().toInt()
    arr = Array(R){Array(C) {' '}}
    alp = Array(R){Array(C) {0}}

    for(i in 0..R-1) {
        var temp = br.readLine()
        for(j in 0..C-1) {
            arr[i][j] = temp[j];
        }
    }

    // 비트레이트 연산
    DFS(0, 0, 1 shl arr[0][0]-'A', 1);
    println(result)
} // End of main

private fun DFS(x : Int, y : Int, bit : Int, count : Int) {

    if(alp[x][y] == bit) return;
    alp[x][y] = bit;

    result = Math.max(result, count);

    for(i in 0..3) {
        nowX = x + dirX[i];
        nowY = y + dirY[i];

        if(nowX<0||nowY<0||nowX==R||nowY==C) continue;
        if( (bit and (1 shl arr[nowX][nowY]-'A')) !=0 ) continue;
        DFS(nowX, nowY, bit or (1 shl arr[nowX][nowY]-'A'), count+1)
    }
} // End of DFS