백준 1987. 알파벳

🅰 백준 1987. 알파벳

1987번: 알파벳

✏️ 문제 풀이

• dr, dc배열을 사용하여 위,아래,좌,우 방향을 저장해주었고 A-Z 까지 아스키코드-65를 해줘서 boolean형 check배열의 크기를 26으로 설정해주었다 (0 : 'A', 1 : 'B' .... 26 : 'Z') 
• 방문한 알파벳은 check에 true표시를 해주었고, 재귀함수 수행 후 다시 돌아왔으면 이전에 방문한 위치를 다시 false표시 해주어서 다른 길로도 갈 수 있도록 해주었다.
• 알파벳을 방문할 때 마다 cnt++을 해줘서 길의 개수를 카운트 해줬고, 위,아래,좌,우 모두 이동할 길이 없으면 for문을 나온 뒤 max값과 비교 후 max에 더 큰 값을 넣어주고, cnt--를 해주었다.(위치가 한단계 이전으로 돌아가기 때문)

✏️ 소스코드

package _0819;

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

public class Main_골드4_1987_손은성 {
	static int max = Integer.MIN_VALUE;
	static char map[][];
	static boolean check[] = new boolean[26];
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };
	static int cnt = 1;
	static int C,R;
	public static void main(String[] args) throws Exception {
		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 char[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);
			}
		}

		check[(int) map[0][0] - 65] = true; // 시작점 true 설정
		search(0, 0);
		System.out.println(max);
	}

	private static void search(int xr, int yc) {
		int r = xr, c = yc;
		int nr = 0, nc = 0;

		//위, 아래, 좌, 우 search하면서 갈 수 있는 길 파악
		for (int i = 0; i < 4; i++) {
			nr = r + dr[i];
			nc = c + dc[i];
			if (nr > -1 && nr < R && nc > -1 && nc < C) {
				if (!check[(int) map[nr][nc] - 65]) {
					cnt++;	// 방문할 때마다 cnt++
					check[(int) map[nr][nc] - 65] = true;//방문했으면 방문한 알파벳 true 표시
					search(nr, nc);
					check[(int) map[nr][nc] - 65] = false; // 다시 돌아왔으면 갔던 길 취소
				}
			}	
		}max = Math.max(max, cnt);
		cnt--; // 방문한 길 돌아오면 cnt--
	}
}

 

✅ 후기

• 골드4라고 어려울거다 생각했으나 문제를 많이 풀어보고 하니 어떤 식으로 접근해야 할지에 대해서 금방 감이 잡혀서 쉽게 풀었다. 코딩도 수학문제처럼 많이 풀어 본 사람이 익숙하고 다양한 방법으로 풀 수 있을것이라는 생각이 들었다.