문제

BOJ 1987: 알파벳 https://www.acmicpc.net/problem/1987

풀이

조건

• (0, 0)부터 시작해서 상하좌우로 이동한다.
• 이 때 이미 지나온 칸에 있는 문자는 다시 방문할 수 없다.

풀이 순서

• map 배열에 입력받을 때 map[i][j] = str.charAt(j) - 'A'; 를 해주어 정수로 입력받는다.
• (0, 0) 부터 DFS를 통해 map 전체를 탐색한다.
• 상하좌우를 탐색한다.
• isIn 배열을 통해 방문한 알파벳은 방문 처리를 해준다.

코드

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

public class Main {
	
	static int R, C; // map 크기
	static int[][] map; 
	static boolean[] isIn = new boolean[26]; // 알파벳 순서대로 지나왔는지 체크할 배열
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	static int max = 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];
		
		for(int i=0; i<R; i++) {
			String str = br.readLine();
			for(int j=0; j<C; j++) {
				map[i][j] = str.charAt(j) - 'A'; // 입력받은 알파벳을 정수로 바꿔서 저장
			}
		}
		
		dfs(0, 0, 0); // 0번째에 (0, 0) 좌표에서부터 시작
		
		System.out.println(max);
	}
	
	static void dfs(int depth, int x, int y) {
		/*
		 * depth: 현재 몇 칸 째인지 넣을 패러미터
		 * x: x좌표
		 * y: y좌표
		 */
		if(isIn[map[x][y]]) { // 이미 지나온 문자라면?
			max = Math.max(max, depth); // 이동한 칸 수의 최댓값 구함
			return;
		} else {
			isIn[map[x][y]] = true; // 현재 문자를 방문 처리
			
			// 4방향 탐색
			for(int t=0; t<4; t++) {
				int nx = x + dx[t];
				int ny = y + dy[t];
				
				// 탐색한 위치가 범위 안에 있다면 DFS 수행
				if(nx >= 0 && ny >= 0 && nx < R && ny < C) {
					dfs(depth + 1, nx, ny);
				}
			}
			
			// 다른 루트로 DFS를 탐색하기 위해 방문 처리한 것을 취소함
			isIn[map[x][y]] = false;
		}
		
	}
	
}

정리

• 종료 조건을 잘 못 설정해줘서 시간 낭비를 했다.