[백준]1987번 알파벳(java)

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

1987번: 알파벳

핵심

이 문제는 DFS를 이용하면 쉽게 풀 수 있다. 또한 알파벳을 이미 방문했는지 판단해야 한다.

 

정답 코드

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

public class Main {
    static int R, C;
    static int[][] map;
    static boolean[] visit = new boolean[26];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int max = 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 str = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j) - 'A';
            }
        }
        dfs(0, 0, 0);
        System.out.println(max);
    }

    public static void dfs(int x, int y, int count) {
        if (visit[map[x][y]]) {
            max = Math.max(max, count);
            return;
        }

        visit[map[x][y]] = true;
        for (int i = 0; i < 4; i++) {
            int moveX = x + dx[i];
            int moveY = y + dy[i];
            if (moveX >= 0 && moveY >= 0 && moveX < R && moveY < C) {
                dfs(moveX, moveY, count + 1);
            }
        }
        visit[map[x][y]] = false;
    }
}

해설

문제를 이해하는 것은 어렵지 않다고 생각한다.

0,0에서 DFS를 한다.

상하좌우로 이동하며, 이 전에 지나온 알파벳은 지나갈 수없다.

만약 중복된 알파벳을 발견하면, 이동거리를 갱신하고 리턴한다.

다른 루트로 DFS 탐색을 하기 위해 visit 배열을 방문하지 않은 상태로 초기화한다.

 

 

배운 점

맨 처음 풀었을 때, 시간초과가 나왔다.

visit를 리스트로 만들어서 만약 list에 포함되어 있다면 리턴 시키고, 방문하지 않은 상태로 만드는 작업은

remove를 사용하였다. 내 생각에 remove 과정에서 많은 시간이 소모되어 시간초과가 뜬 것 같다.

List가 편하고 간편하고 단순해 막 사용하는 경향이 있는데, 좀 더 신중히 생각하고 사용해야겠다.