[Eric's 백준] 1987번 - 알파벳 - Java

문제

오늘도 백준문제 달리는 Eric입니다!

오늘 풀어볼 문제는 백준 1987번 알파벳 이라는 문제 입니다.

일반적인 dfs 문제랑 다르게,

graph가 0과 1로 이루어 진것이 아니라,

알파벳으로 이루어져 있고, 이미 지나간 알파벳은 다시 지날 수 없다는 조건이 있습니다.

 

그래서 저는 이 부분을 boolean[] visited = new boolean[26] 으로 설정하고

만약 해당 칸을 지나가면, 값을 true로 변경하도록 하였습니다.

 

그리고 dfs를 돌면서 만약 해당 graph 위치에 도착했을때 

visited가 false 이면 상,하,좌,우 로 이동하면서 

dfs를 반복합니다.

만약 돌다가 visited가 true 이면 이미 지나갔던 알파벳을 만난것이므로 answer 에 max 값으로 입력합니다.

 

그리고 44번줄에서 false 로 만든 이유는 

이미 지나간 max 값 보다 더 높은 max 값이 나올 수 있는 다른 dfs 경로를 지나가기 위해서

초기화 해줍니다.

 

코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.*;
	public class N1987 {
	static int R, C;
	static int[][] graph;
	static boolean[] visited = new boolean[26]; // 알파벳이 26개 니까
	static int[] dx = {1, 0, 0, -1};
	static int[] dy = {0, 1, -1, 0};
	static int answer = 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());
	graph = new int[R][C];
	for (int i = 0; i < R; i++) {
	String tmp = br.readLine();
	for (int j = 0; j < C; j++) {
	graph[i][j] = tmp.charAt(j) - 'A';
	}
	}
	dfs(0, 0, 0);
	System.out.println(answer);
	br.close();
	}
	public static void dfs(int x, int y, int cnt) {
	if (visited[graph[x][y]]) { // 이미 지나간 알파벳이면 true
	answer = Math.max(answer, cnt); // 지나간 곳의 알파벳을 다시 만났다면 answer 는 cnt.
	return;
	} else {
	visited[graph[x][y]] = true; // 현재 말이 있는 곳의 알파벳 체크
	for (int i = 0; i < 4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (nx >= 0 && ny >= 0 && nx < R && ny < C) {
	dfs(nx, ny, cnt + 1); // cnt 증가
	}
	}
	visited[graph[x][y]] = false; // 다른 루트로 dfs를 탐색하기 위해서
	}
	}
	}

view raw N1987.java hosted with ❤ by GitHub