BOJ_G4_1987
π [G4_1987] μνλ²³
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static StringTokenizer st;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static int R, C;
static boolean[][] isChecked;
static int nx,ny;
// μ΄ νμ μΉ΄μ΄ν
static int cnt;
static int max = Integer.MIN_VALUE;
static boolean[] alp;
static char[][] arr;
static int i =0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine(), " ");
// μΈλ‘
R = Integer.parseInt(st.nextToken());
// κ°λ‘
C = Integer.parseInt(st.nextToken());
// μ
λ ₯κ° μ μ₯
arr = new char[R][C];
// μ§λκ°λμ§ μ²΄ν¬
isChecked = new boolean[R][C];
// μ 체ν¬
alp = new boolean[26];
// λ°°μ΄ μ
λ ₯
for (int i = 0; i < R; i++) {
String str = br.readLine();
for (int j = 0; j < C; j++) {
arr[i][j] = str.charAt(j);
}
}
check(0,0);
System.out.println(max);
}
static void check(int x, int y) {
if(x < 0 || x == R || y < 0 || y == C || alp[(arr[x][y]-65)] == true) {
return;
}
// λ°©λ¬Έμ μνμΌλ©΄ trueλ‘ λ°κΏμ£Όκ³ νλ μΉ΄μ΄ν
alp[(arr[x][y]-65)] = true;
cnt++;
max = Math.max(max, cnt);
for (int z = 0; z < 4; z++) {
nx = dx[z] + x;
ny = dy[z] + y;
check(nx,ny);
}
alp[(arr[x][y]-65)] = false;
cnt--;
}
}
π€ λμ μκ°
λ¬Έμ λ₯Ό λ³΄κ³ λ¨Όμ μμκ° μκ΄μ΄ μκΈ° λλ¬Έμ μμ΄λ‘ νμ΄μΌ κ² λ€λ μκ°μ΄ λ€μλ€.
κ·Έλ¦¬κ³ μνλ²³μ΄ μ¬μ©λμλμ§ μ 무λ₯Ό νμ
νκΈ° μν΄ 26κ°μ μμλ₯Ό κ°μ§ boolean λ°°μ΄κ³Ό κ³μ°μ μμ€ν€μ½λλ₯Ό μ΄μ©νμ¬ 0->A, 1->B .. μ΄λ°μμΌλ‘ μ ν΄μ£Όμλ€.
κ·Έλ¦¬κ³ μ¬κ·λ‘ κ°λ€μμλ λ°±νΈλνΉμ ν΅ν΄ μ’ λ ν¨μ¨μ μΈ μ½λλ₯Ό μμ±νμλ€.
μ²μ μμΉλΆν° 4λ°©ν₯ νμμ ν΅ν΄ λ€μ μμλ₯Ό μ ν΄μ£Όμλ€.
κ²°λ‘ μ μΌλ‘λ DFSμ λ°±νΈλνΉμ λν΄ μ’ λ 곡λΆνκ² λλ λ¬Έμ μλ€.