[백준_1987번] 알파벳

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

1987번: 알파벳

[문제]

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

 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1987 {
	public static char[][] board;
	/*
	 * visited 배열은 해당 보드에 적혀있는 알파벳을
	 * 이전에 지나온 적이 있는지 체크하는 배열이다. 
	 */
	public static boolean[] visited=new boolean[26]; 
	public static int[] dx= {-1,1,0,0};
	public static int[] dy= {0,0,-1,1};
	public static int r,c,max=Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		r=sc.nextInt();
		c=sc.nextInt();
		board=new char[r][c];
		
		// 보드 정보 입력 받기
		for(int i=0;i<r;i++) {
			String str=sc.next();
			for(int j=0;j<c;j++) {
				board[i][j]=str.charAt(j); 
			}
		}
		
		dfs(0,0,1);
		System.out.println(max);
	}
	
	// 백트래킹
	public static void dfs(int x, int y, int count) {
		visited[board[x][y]-'A']=true; // 방문처리
		
		// 이동할 수 있는 상,하,좌,우 탐색
		for(int i=0;i<4;i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			/*
			 * 이동한 좌표가 범위 내에 있고 
			 * 이전에 지나온 칸에 적혀있는 알파벳이 아니라면 
			 * 이동한 칸의 개수를 +1해주고 재귀호출한다.
			 */
			if(nx<r&&nx>=0&&ny<c&&ny>=0) {
				if(visited[board[nx][ny]-'A']==false) {
					dfs(nx,ny,count+1);
				}
			}
		}
		
		// 재귀호출이 끝난다면 다음 탐색을 위해 값을 되돌려준다.
		visited[board[x][y]-'A']=false;
		max=Math.max(max, count); // 이동한 칸수 최댓값 갱신
	}
}

 

[고찰]

 해당 문제를 처음에는 BFS로 해결하여 했다. 하지만 마지막 예제에서 자꾸 오답이 출력되어 무엇이 문제인지 알기위해 다른 사람의 코드를 참고하였다. 

 이번 문제는 BFS로 풀면 오답을 받을 수 밖에 없었다. 그 이유는 BFS를 사용하면 동시에 같은 레벨의 다른 접점을 접근하기 때문에 만약 2레벨의 같은 알파벳이 있으면 방문 여부를 파악하기가 힘들기 때문이다. 따라서 백트래킹을 사용하여 가능한 경로를 모두 탐색 후 이동한 경로가 가장 긴 값을 구해야 한다. 

 위의 아이디어는 생각해내지 못했는데 해당 예제를 여러번 복습해보면서 익숙해지게 만들어야겠다.