[BOJ/Java] 백준 1987번 - 알파벳

백준 #1987 알파벳

1987번: 알파벳

 

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

public class Main {
	
	static int R, C, maxDist;
	static char[][] map;
	static HashMap<Character, Integer> alpha;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		R = Integer.parseInt(st.nextToken());  // 행
		C = Integer.parseInt(st.nextToken());  // 열
		map = new char[R][C];
		for (int i = 0; i < R; i++) {
			String line = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = line.charAt(j);
			}
		}
		// 알파벳 hash map 생성
		// 지나간 알파벳은 1, 지나가지 않은 알파벳은 0 으로 표시
		alpha = new HashMap<Character, Integer>();
		char ch = 'A';
		for (int i = 0; i <26 ; i++) {
			alpha.put((char)(ch + i), 0);
		}
				
		alpha.put(map[0][0], 1);
		dfs(0, 0, 1);
		sb.append(maxDist);
		System.out.println(sb);
	}
	
	public static boolean inRange(int x, int y) {
		return 0 <= x && x < R && 0 <= y && y < C;
	}
	
	public static void dfs(int x, int y, int dist) {

		for (int i = 0; i < 4; i++) {			
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (inRange(nx, ny)) {
				if (alpha.get(map[nx][ny]) == 1) {  // 이미 지나간 알파벳일 경우
					maxDist = Math.max(maxDist, dist);
					continue;
				}
				alpha.put(map[nx][ny], 1);
				dfs(nx, ny, dist+1);
				alpha.put(map[nx][ny], 0);
			}
		}
		return;
	}
}

dfs 탐색을 하면서 지나온 알파벳만 표시해주면 된다. 여기서 알파벳 표시를 어떻게 해주냐에 따라 시간 초과가 나고 안 나고가 결정되는 것 같다.

파이썬이었으면 리스트 사용해서 not in 을 사용했을 것 같은데, 자바에서는 hashMap을 이용해서 표시해주었다. 알파벳 전체를 key 값으로 한 hashMap을 만들어준 후 지나온 알파벳은 1로, 아직 지나가지 않은 알파벳은 0으로 value 값을 넣어주었다. 

 

++ 더 최적의 방법

알파벳 개수 크기의 boolean 배열을 만들어준 후, 알파벳 아스키 코드를 인덱스로 사용해주었다. A 부터 차례대로 65, 66 ..  순으로 올라가기 때문에 알파벳에서 65를 빼주면 인덱스로 활용 가능하다.

알파벳 hashMap을 초기화하지 않아도 돼서 기존 코드보다 약 2배 이상 빠르다!

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

public class Main {
	
	static int R, C, maxDist;
	static char[][] map;
	static boolean[] visited;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		R = Integer.parseInt(st.nextToken());  // 행
		C = Integer.parseInt(st.nextToken());  // 열
		map = new char[R][C];
		for (int i = 0; i < R; i++) {
			String line = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = line.charAt(j);
			}
		}
		
		// 지나온 알파벳 표시하는 visited 배열
		// index: 알파벳 - 65
		visited = new boolean[26];
		visited[map[0][0]-65] = true;
				
		dfs(0, 0, 1);
		sb.append(maxDist);
		System.out.println(sb);
	}
	
	public static boolean inRange(int x, int y) {
		return 0 <= x && x < R && 0 <= y && y < C;
	}
	
	public static void dfs(int x, int y, int dist) {

		for (int i = 0; i < 4; i++) {			
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (inRange(nx, ny)) {
				if (visited[map[nx][ny]-65]) {  // 이미 지나간 알파벳일 경우
					maxDist = Math.max(maxDist, dist);
					continue;
				}
				visited[map[nx][ny]-65] = true;
				dfs(nx, ny, dist+1);
				visited[map[nx][ny]-65] = false;
			}
		}
		return;
	}
}

 

---

이전에 풀었던 내역

[모각코] 210811 Today I Learned