백준 1987번 알파벳

문제

백준 1987번 알파벳 링크

풀이 방법

간단한 DFS 문제다. visited[] 배열을 각 문자열에 대해서 만들고 이미 방문한 문자를 방문하지 않게 하는 방식으로 풀어나가면 된다.

1. 문자열에 대해 visited 배열 만들기

문제에서 대문자들로 배열이 주어지므로 아스키 코드로 65번부터 90번까지의 문자이다. 따라서 visited[] 배열의 크기를 26으로 만들고 각각 인덱스를 문자 - 65로 생각하면된다.

2. DFS 구현하기

일반적인 DFS와 똑같이 구현하면 된다.

static void DFS(int r, int c, boolean[] visited) {
	int idx = arr[r][c] - 65; // 현재 문자의 아스키 코드
	if(!visited[idx]) { // 방문한 적 없으면
		visited[idx] = true;
		for(int i=0 ;i<4; i++) {
			int newX = c + dx[i];
			int newY = r + dy[i];
			if(check(newX, newY)) {
				DFS(newY, newX, visited);
			}
		}
		// 나올 때는 visited를 false로 바꿔줌
		visited[idx] = false;
	}else { // 방문 했으면
		// max 업데이트
		int cnt = 0;
		for(int i=0; i<26; i++) {
			if(visited[i]) {
				cnt++;
			}
		}
		if(max < cnt) max = cnt;
	}
}

3. max 업데이트 후 출력하기

만약 이미 방문한 문자라면 현재 visited[] 배열에서 방문한 것들을 센 후 max와 비교하여 max를 업데이트 해준다. 여기서 max는 최대 몇칸을 갈 수 있는지를 나타낸다.

정답 코드

package 백준;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class p1987 {
	static int R, C;
	static int [] dx = {-1, 0, 0, 1};
	static int [] dy = {0, 1, -1, 0};
	static char [][] arr;
	static int max = 1;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		arr = new char [R][C];
		
		for(int i=0; i<R; i++) {
			
			String line = br.readLine();
			for(int j=0; j<C; j++) {
				arr[i][j] = line.charAt(j);
			}
		}
		
		
		boolean [] visited = new boolean[26];
		DFS(0, 0, visited);
		bw.write(max+"");
		bw.flush();
		bw.close();
		// DFS
	}	
	
	static void DFS(int r, int c, boolean[] visited) {
		int idx = arr[r][c] - 65; // 현재 문자의 아스키 코드
		if(!visited[idx]) { // 방문한 적 없으면
			visited[idx] = true;
			for(int i=0 ;i<4; i++) {
				int newX = c + dx[i];
				int newY = r + dy[i];
				if(check(newX, newY)) {
					DFS(newY, newX, visited);
				}
			}
			// 나올 때는 visited를 false로 바꿔줌
			visited[idx] = false;
		}else { // 방문 했으면
			// max 업데이트
			int cnt = 0;
			for(int i=0; i<26; i++) {
				if(visited[i]) {
					cnt++;
				}
			}
			if(max < cnt) max = cnt;
		}
	}
	
	static boolean check(int x, int y) {
		return y<R && y>=0 && x<C && x>=0;
	}
}