백준 1987 알파벳 [자바]

05 Jun 2022 in Develop / Solving

baekjoon 1987 알파벳

java

문제 분석

• R행 C열의 보드의 각 칸에 알파벳이 써져 있음.
• 왼쪽 위에서 시작하여, 상하좌우로 움직이는 데 같은 알파벳은 한번만 밟으면서 이동해야 함.
• 말이 지날 수 있는 최대 칸은?

입력조건

행 수 R, 열 수 C
R행 C열의 영문배열

풀이과정

• dfs + 백트래킹
• visited 배열을 만드는 데, 2차원으로 R*C만큼 만드는 것이 아니라, 알파벳의 수 만큼 만들어서(26개) 내가 있는 위치의 알파벳을 통과했는지 아닌지를 판단.

전체 코드

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

public class BJ1987_알파벳 {
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	static int R, C;
	static int maxrun = 0;
	public static boolean[] visited = new boolean[26];
	static int[][] map;
	
	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];
		for(int i = 0; i < R; i++) {
			String ref = br.readLine();
			for(int j = 0; j < C; j++)
				map[i][j] = ref.charAt(j) - 'A';
		}
		
		visited[map[0][0]] = true;
		run(0, 0, 1);
		
		System.out.print(maxrun);
	}
	public static void run(int r, int c, int len) {
		for(int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
			// 더 갈 수 없으면 비교
			if(visited[map[nr][nc]]) {
				maxrun = Math.max(len, maxrun);
				continue;
			}
			
			visited[map[nr][nc]] = true;
			run(nr, nc, len+1);
			visited[map[nr][nc]] = false;
		}
	}
}