[백준/자바] 1987: 알파벳

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

1987번: 알파벳

---

위 문제는 그래프를 이용해 최대값을 구하는 문제이다.

보통 그래프 관련 문제로는 BFS를 이용한 최단거리, 최소값 문제를 많이 풀었어서 처음에는 조금 낯설었다.

 

최대값을 구하는 문제에서는 DFS를 많이 사용한다.

가능한 모든 루트를 돌아 최대값을 구해야 하는데 visited 처리 부분에서 어려움을 겪었다.

백트래킹을 통해 DFS가 리턴되면 해당 좌표 visited를 false 처리해 다른 루트로 가는 경우의 수도 확인할 수 있게 하였다.

 

풀이과정은 다음과 같다.

1. 입력값(문자열)을 아스키 코드 형식으로 2차원 배열에 저장

2. 초기값(x = 0, y = 0, count = 0)을 넣어 dfs 실행

 

DFS 함수

- 입력받은 좌표의 알파벳이 사용되었는지 확인

   - 사용되었으면 count값 갱신 후 return

   - 사용되지 않았으면 이동 가능한 좌표를 인수로 넣어 dfs 재귀 실행

     * for문 전 후로 visited 값 변경

     * 완료 후 다른 가능한 루트도 확인하기 위해 방문 여부 false로 변경

 

import java.util.*;
import java.io.*;

public class Main {

	static int R, C;
	static int ans = 0;
	static int[][] board;
	static boolean[] visited = new boolean[26];
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -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());

		board = new int[R][C];
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				board[i][j] = str.charAt(j) - 'A'; // -A 통해 아스키 코드값 구함
			}
		}

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

	static void dfs(int x, int y, int count) {
		if (visited[board[x][y]]) {
			ans = Math.max(ans, count);
			return;
		} else {
			visited[board[x][y]] = true;
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
					dfs(nx, ny, count + 1);
				}
			}
			// 방문 여부를 false로 갱신해 다른 루트도 확인할 수 있게 한다.
			visited[board[x][y]] = false;
		}
	}
}

 

DFS를 사용할 때 백트래킹도 함께 사용되는 경우가 많으니 참고!