[백준] 1987_알파벳

김태민·2022년 5월 20일
0

알고리즘

목록 보기
70/77

mingssssss

1. 문제

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


문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

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

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

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

2. 코드

package mymain;

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

public class BOJ_1987 {

	static int N;
	static int M;
	static char[][] list;
	static boolean[] visited;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int answer = Integer.MIN_VALUE;
	static int cnt;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		list = new char[N][M];
		visited = new boolean[26];

		for (int i = 0; i < N; i++) {
			String[] temp = br.readLine().split("");
			for (int j = 0; j < M; j++) {
				list[i][j] = temp[j].charAt(0);
			}
		}
		// 입력 종료

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

		// 출력
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < M; j++) {
//				System.out.printf("%s ", list[i][j]);
//			}
//			System.out.println();
//		}

	}

	private static void dfs(int r, int c, int cnt) {

		if (visited[list[r][c] - 'A'] == true) {
			answer = Math.max(answer, cnt);
			return;
		}

		visited[list[r][c] - 'A'] = true;

		for (int i = 0; i < 4; i++) {

			int nextX = r + dx[i];
			int nextY = c + dy[i];

			if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
				continue;
			}

			dfs(nextX, nextY, cnt + 1);

		}
		visited[list[r][c] - 'A'] = false;
	}

}

3. 리뷰

숫자 대신 알파벳으로 탐색하는 문제이다.

처음 시작 지점(0, 0)부터 탐색해서 최대로 갈 수 있는 거리를 구하는 문제이다.

원래라면 bfs로 구현해서 풀었겠지만.. 지금은 dfs 공부 중이여서 dfs로 구현했다.

일반적인 숫자 탐색이 아닌, 알파벳 탐색이라 char형으로 받아와서

대문자 알파벳 시작점인 'A'를 빼줘서 방문체크를 했다.

나머지는 문제가 없었지만, 각 dfs에서 cnt를 어떻게 체크하고

어떻게 방문 배열을 초기화 해야 하는지 생각하기가 어려웠다.

구글링을 통해 dfs를 돌 때마다 cnt + 1을 해줘서 dfs로 갈 수 있는

최대 거리를 구하는 개념이였다. 간단하지만 이해하기 어려워서 디버깅을 통해

cnt가 어떤식으로 증가하는지 고민해봐야겠다.

또한 for문을 벗어나는 경우, 해당 방문 배열을 초기화 하는 개념을 공부했다.

for문을 벗어난다는 것은 해당 좌표에서 갈 수 있는 곳이 없다는 의미므로

해당 방문 배열은 false로 체크한다.

전체적인 풀이 방향은 알겠는데, 이를 dfs로 구현하는 것이 쉽지 않았다.

다양한 문제를 풀어보면서 연습해야겠다.

profile
어제보다 성장하는 개발자

0개의 댓글