[Gold IV] 알파벳 - 1987

문제 링크

성능 요약

메모리: 15112 KB, 시간: 1084 ms

분류

백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 7월 11일 14:59:40

문제 설명

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

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

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

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

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

입력

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

출력

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

풀이 (DFS)

처음에 이 문제를 접했을 때, Set 을 사용해서 해결하는 문제라고 생각해 visited 배열과 Set을 둘 다 사용해 코드를 짰었다...
한참을 고민하다 visited 배열을 알파벳을 체크하는 방식으로 푸는 풀이를 보고 해결했다.

만약 본인이 Set으로 풀고 싶다면 [Set 풀이 블로그] 를 참고해도 좋을 것 같다.

풀이 방식
1. (0,0)을 시작으로 상하좌우로 움직이면서 알파벳을 탐색한다.
2. 알파벳 배열을 통해 해당하는 알파벳을 체크해간다.
3. 만약 이미 체크된 알파벳에 도착할 경우 답을 갱신하고 리턴한다.

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

public class Main {
	//dfs 문제
	static boolean[] visited=  new boolean[26]; //같은 알파벳 체크 여부 확인
	static int map[][]; //입력 배열
	static int R,C; //크기
	static int[] dx = {1,-1,0,0}; //동서남북 이동
	static int[] dy = {0,0,1,-1};
	static int ans=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());
		map = new int[R][C];
		
		
		for(int i=0; i<R; i++) {
			String temp = br.readLine();
			for(int j=0; j<C; j++) {
				map[i][j]=temp.charAt(j)-'A';
			}
		}
		
		dfs(0,0,0);
		
		if(ans==0) { //처음 무조건 하나는 방문한다.
			ans=1;
		}
		System.out.println(ans);
	}
	
	public static void dfs(int x,int y, int cnt) {
		if(visited[map[x][y]]) { //같은 알파벳이 이미 방문했다면
			ans = Math.max(ans, cnt);
			return;
		}
		visited[map[x][y]]=true; 
			
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx>=R || ny >=C || nx<0 || ny <0) {
				continue;
			}
			dfs(nx,ny,cnt+1);
		}
		visited[map[x][y]]=false;	
	}
}