[BJ1987] 알파벳

 백준 - 알파벳 

문제 링크

https://www.acmicpc.net/problem/1987

1987번: 알파벳

 

문제 입출력

2 4
CAAB
ADCB
3 6
HFDFFB
AJHGDH
DGAGEH
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

3
6
10

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
	static int ans, R, C;
	static char[][] map;
	static boolean[] visit = new boolean[26]; // 이때까지 지나온 알파벳

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };


	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("input.txt"));
		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][];

		// 초기화
		ans = Integer.MIN_VALUE;

		for (int i = 0; i < R; i++) map[i] = br.readLine().toCharArray();

		// 탐색
		visit[map[0][0] - 'A'] = true;
		dfs(0, 0, 1);

		// 출력
		System.out.println(ans);
	} // end main


	// 한칸씩 이동해서 말을 놓는 함수
	private static void dfs(int y, int x, int max) {
		ans = Math.max(ans, max);

		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
			if (visit[map[ny][nx] - 'A']) continue;

			visit[map[ny][nx] - 'A'] = true;
			dfs(ny, nx, max + 1);
			visit[map[ny][nx] - 'A'] = false;
		}

	} // end dfs

}

• dfs, bfs 를 이용하여 풀 수 있습니다. 저는 dfs 를 이용하였습니다.
• 현재 자리의 알파벳이 이때까지 visit 했던 알파벳과 달라야합니다.
• 따라서 26 자리의 알파벳 배열을 만들어주고 만약 visit 을 했다면 true 처리를 해줍니다.
• 그리고 나서 상하좌우에서 따져보고, max 값을 세기 위해 백트랙킹이 필요하므로 false 로 원복을 시켜줍니다.

 

 

 

 

 

 

 

 

 

# 백준 알파벳 java # 백준 알파벳 dfs java

---