BOJ 1987

2020-08-17

위 문제는 백준 사이트의 알고리즘 1987 문제에 관한 설명입니다.

BOJ 1987

알파벳

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다.

보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데,

새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다.

즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오.

말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다.

(1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Main {
	static int R, C, answer;
	static int[][] map;
	static boolean[] visit = new boolean[26];
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	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());
		map = new int[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) - 'A';
			}
		}
		answer = 0;

		dfs(0, 0, 0);
		System.out.println(answer);
	}

	private static void dfs(int x, int y, int count) {
		if (visit[map[x][y]]) {
			answer = Math.max(answer, count);
			return;
		} else {
			visit[map[x][y]] = true;
			for (int i = 0; i < 4; i++) {
				int nextX = x + dx[i];
				int nextY = y + dy[i];
				if (0 <= nextX && 0 <= nextY && nextX < R && nextY < C) {
					dfs(nextX, nextY, count + 1);
				}
			}
			visit[map[x][y]] = false;
		}
	}
}

이번 문제는 BFS을 이용해서 풀었습니다.

이번 문제의 해결법은?

(0,0) 부터 시작해서, R x C의 크기를 가지는 map을 상하좌우로 이동을 하면서 dfs 탐색을 시작합니다.

이 전에 지나온 알파벳은 지나갈 수 없다는 조건을 만족하기 위해 visit 배열을 만들어주고,

알파벳을 방문했다면 true로 바꾸면서 중복 여부를 판단합니다.

중복된 알파벳을 발견하였다면 이동거리를 갱신하고 리턴합니다.

다시 나왔을 때, DFS로 다른 루트를 가는 경우까지 고려하기 위해 visit 배열을 방문하지 않은 상태로 초기화 해줍니다.

알파벳