[백준/자바] 1987번: 알파벳

문제

https://www.acmicpc.net/problem/1987

풀이

• 세로 R칸, 가로 C칸으로 이루어진 보드
• 각 칸에는 대문자 알파벳이 하나씩 적혀있고, 좌측 상단 칸(1행 1열)에는 말이 놓여 있다.
• 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동 가능
• 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다.
• 1행 1열에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지 출력
  • 말이 지나는 칸은 출발점도 포함

DFS와 백트래킹을 활용하는 문제

상하좌우 탐색을 진행하며, 방문한 알파벳이 아니라면 진행하면 됩니다.

입력

		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		graph = new int[r][c];
		for (int i = 0; i < r; i++) {
			String s = br.readLine();
			for (int j = 0; j < c; j++) {
				graph[i][j] = s.charAt(j) - 'A';
			}
		}

• graph: 보드
• int 배열로 선언하였습니다.
• char에서 A를 빼주면 0 ~ 25의 수로 알파벳을 저장할 수 있습니다.

탐색

	private static void dfs(int depth, int sr, int sc) { // 길이, 현재 좌표
		if (answer < depth) { // 더 클 경우 업데이트
			answer = depth;
		}
		
        // 4방 탐색
		for (int i = 0; i < 4; i++) {
			int nr = sr + dr[i];
			int nc = sc + dc[i];
			
			if (nr < 0 || nr >= r || nc < 0 || nc >= c) continue; // 범위 밖이면 지나침
			if (visited[graph[nr][nc]]) continue; // 방문한 알파벳이면 지나침
			
			visited[graph[nr][nc]] = true; // 방문 처리
			dfs(depth + 1, nr, nc); // 다음 좌표로 진행
			visited[graph[nr][nc]] = false; // 백트래킹
		}
	}

• 방문한 알파벳이 아닐 경우 진행
• 다음 좌표까지 탐색이 끝났다면, 방문 처리한 알파벳을 다시 false처리해 백트래킹해 줍니다.

코드

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

public class Main {
	static int r, c;
	static int[][] graph;
	
	static int answer = 0;
	static boolean[] visited = new boolean[26];
	
	static final int[] dr = { -1, 1, 0, 0 };
	static final int[] dc = { 0, 0, -1, 1 };
	
	private static void dfs(int depth, int sr, int sc) {
		if (answer < depth) {
			answer = depth;
		}
		
		for (int i = 0; i < 4; i++) {
			int nr = sr + dr[i];
			int nc = sc + dc[i];
			
			if (nr < 0 || nr >= r || nc < 0 || nc >= c) continue;
			if (visited[graph[nr][nc]]) continue;
			
			visited[graph[nr][nc]] = true;
			dfs(depth + 1, nr, nc);
			visited[graph[nr][nc]] = false;
		}
	}
	
	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());
		
		graph = new int[r][c];
		for (int i = 0; i < r; i++) {
			String s = br.readLine();
			for (int j = 0; j < c; j++) {
				graph[i][j] = s.charAt(j) - 'A';
			}
		}
		
		visited[graph[0][0]] = true;
		dfs(1, 0, 0);
		System.out.println(answer);
	}

}