백준 1987 알파벳 (Java)

1. 문제 링크

1987번: 알파벳

 

2. 문제 및 입출력예제

 

3. 문제 풀이

입력받은 map을 dfs로 탐색한다.

알파벳은 boolean 배열을 이용해서 들렀는지 아닌지 확한다.

방향벡터를 이용해서 범위 안에 있을때 방문했던 위치인지 확인하고 재귀한다.

 

처음에 한 칸이 기본이니까 값을 세는 시작이 1이라는 점도 꼭 챙겨야 한다.

 

4. 코드

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

public class Main {
	static int R, C, map[][], al[], max, now;
	static boolean[] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] rc = br.readLine().split(" ");
		R = Integer.parseInt(rc[0]);
		C = Integer.parseInt(rc[1]);
		map = new int[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)- 65;
			}
		} //입력 끝
		visit = new boolean[26];
		max = 1;
		now = 1;
		round(0, 0);
		System.out.println(max);
		
	}
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	private static void round(int x, int y) {
		int start = map[x][y];
		visit[start] = true;
		
		for(int d=0;d<4;d++) {
			int curX = x + dx[d];
			int curY = y + dy[d];
			
			if(curX<0 || curX>=R || curY<0 || curY>=C) continue;
			int cur = map[curX][curY];
			if(visit[cur]) continue;
			max = Math.max(max, ++now);
			
			round(curX, curY);
		}
		now--;
		visit[start] = false;
		
	}
}