(Java/자바) - 백준(BOJ) 1987번 : 알파벳

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

1987번: 알파벳

---

• 문제 : 

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

 

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

 

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

 

 

 

---

• 풀이 :

행렬에서의 탐색 문제였습니다.

 

풀이는 다음과 같습니다.

 

 

1. 입력을 받고 board를 설정한다. 이 때, 보드 바깥으로 벗어나는 경우를 탐지하는 if문을 사용하지 않기 위해 2차원배열에 테두리를 두르고 시작좌표인 board[1][1]의 값을 넣어주었다. (무조건 탐색하지 않으므로)

 

2. visited는 길이 26의 boolean형 배열로 문자 'A' - 'Z' 까지의 방문여부를 표기하기 위해 사용하였다.

 

3. DFS 방식으로 탐색을 실시힌다. 상,우,하,좌의 순서로 다음 진행할 좌표의 알파벳값을 확인하고 만약 방문하지 않은 알파벳이라면 (visited가 false라면) 방문처리하고 다음 탐색을 실시한다.

 

4. 다음좌표로 탐색이 가능할 경우 answer과 현재 탐색한 길이를 비교하여 최댓값으로 갱신해준다.

 

 

 

 

---

• 소스코드 : 

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

public class Main{
	static int R, C;
	static int answer=1;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	static boolean[] visited = new boolean[26];
	static char[][] board;
	static String input;
	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());
		board = new char[R+2][C+2];
		for (int i = 1; i <= R; i++) {
			input = br.readLine();
			for (int j = 0; j < C; j++) {
				board[i][j+1] = input.charAt(j);
			}
		}
		Arrays.fill(board[0], board[1][1]);
		Arrays.fill(board[R+1], board[1][1]);
		for (int i = 0; i < R+2; i++) {
			board[i][0] = board[1][1];
			board[i][C+1] = board[1][1];
		}
		visited[board[1][1]-'A'] = true;
		
		dfs(1,1,1);
		System.out.println(answer);
	}
	private static void dfs(int x, int y, int len) {
		int ax,ay;
		
		for (int i = 0; i < 4; i++) {
			ax = x + dx[i];
			ay = y + dy[i];
			if(!visited[board[ax][ay]-'A']) {
				visited[board[ax][ay]-'A'] = true;
				answer = Math.max(answer, len+1);
				dfs(ax,ay,len+1);
				visited[board[ax][ay]-'A'] = false;
			}
		}
		
	}
	
	
	
}