[백준 1987번] 알파벳 - java

문제 설명

1. 보드에 문자를 통해 x, y축 표를 입력받는다.

2. 말은 왼쪽 맨 위에 위치한다.

3. 말은 상, 하, 좌, 우로 움직일 수 있으며 한번 지나온 칸은 다시 지날 수 없다.

4. 말이 시작해서 최대로 움직일 수 있는 칸을 return하면 된다.

 

 

풀이 과정

 1. 간단한 DFS문제이며, check할 때에 조금만 주의하면 된다.

 2. 각 움직이는 DFS의 진행마다 check의 기준을 다르게 해 주면 될 것이다.

 3. 즉, (위, 아래, 오른쪽, 왼쪽)을 1DFS라고 치면, 1DFS - 2DFS - 3DFS...마다 check를 판단하고 이전의 DFS로 돌아가면 해당 check를 초기화한다.

 4. char로 구할 필요 없이 int로 판단하고, A~Z까지 모든 경우를 check에 넣고 판단하면 더 쉬울 것이다.

 5. 알고리즘 진행 과정은 다음과 같다.

      - 값의 입력을 진행한다.

      - DFS는 말의 위치 기준으로 위, 아래, 좌, 우로 이동 가능한 경우 진행한다.

      - 이미 지나온 위치인 경우 말이 그곳 이후로는 진행 불가능하니 해당 위치에서의 DFS를 멈추고 지금까지 움직인 거리를 return한다.

      - 이미 지나오지 않은 경우 지나왔다는 표시를 알파뱃에 해 주고, DFS를 더 진행해 준다.

 

 

 

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.*;
	public class Main {
	// 테이블 크기 map 적용
	public static int map[][];
	// A~Z 26개가 있는데, 이를 그냥 0~25로 넣고 check하도록 한다. (check 기본값 false)
	public static boolean check[] = new boolean[26];
	// 말은 위, 아래, 상, 하로 움직일 수 있으니 X축 움직임, Y축 움직임을 추가한다.
	public static int Xmove[] = {-1, 1, 0, 0};
	public static int Ymove[] = {0, 0, -1, 1};
	// 테이블 크기를 입력받는 R, C이다.
	public static int R;
	public static int C;
	// 정답 return용 ans
	static int ans = 0;
	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 int[R][C];
	// 테이블 수 만큼 알파뱃을 테이블의 위치에 배정받는다.
	// char을 사용할 필요 없이 A의 아스키 코드만큼 뺴주면 A~Z는 0~25가 된다.
	for (int i = 0; i < R; i++) {
	String s = br.readLine();
	for (int j = 0; j < C; j++) {
	map[i][j] = s.charAt(j) - 'A';
	}
	}
	// 왼쪽 상단 (0, 0) , 시작 내용 0 - DFS시작
	DFS(0, 0, 0);
	System.out.println(ans);
	}
	public static void DFS(int x, int y, int now) {
	// 이미 지나온 알파뱃이면 DFS를 멈추고 값을 판별함
	if(check[map[x][y]]) {
	ans = Math.max(ans, now);
	return;
	}
	// 지나오지 않은 길이면 지나왔다고 check에 true로 표시해 준다.
	check[map[x][y]] = true;
	// 상하좌우 판단해서 움직일 수 있는 경우 DFS를 진행하고, now+1로 한칸 이동한 것을 나타내 준다.
	for(int i=0; i<4; i++) {
	if(x+Xmove[i]>=0 && y+Ymove[i]>=0 && x+Xmove[i] < R && y+Ymove[i] < C) {
	DFS(x+Xmove[i], y+Ymove[i], now+1);
	}
	}
	// 가장 중요한 부분인데, 현재 위치 상하좌우에 대한 DFS가 모두 끝났다는 것은, 현재 위치에서 파생되어 더 움직이는 위치가 없다는 것을 의미한다.
	// 그렇다면 이후에 DFS에서 행해질 것은 현재 위치로 오지 않은 경우의 DFS라는 것이다.
	// 따라서 현재 위치의 모든 판단이 끝나면 check를 다시 false로 돌려 다른 DFS할 때에 문제가 발생하지 않도록 한다.
	check[map[x][y]] = false;
	}
	}

view raw 알파뱃 hosted with ❤ by GitHub