(JAVA) [BOJ]백준 1987번, 알파벳

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

1987번: 알파벳

 

1987, 알파벳

📌 난이도 : Gold 4

📌 알고리즘 : DFS 완전탐색

이번 문제는 DFS로 쉽게 풀었다가 틀려서 1시간 정도 고생했었다. DFS 접근하지만 최대값을 구해야 하기 때문에 완전 탐색으로 모든 구역을 탐색해야 한다는 점을 주의해야 한다.

 

📚 Process

초기화 및 선언

: 알파벳을 순서대로 char[][] map 에 넣어주는 것으로 시작한다. 알파벳을 사용했는지 확인하기 위해 boolean[] alpha 를 추가로 선언해준다.

 

DFS

: 다른 DFS 와 비슷하게 시작한다. 주의할 점은 탐색한 범위, count를 인자로 넘겨준다. 이는 DFS가 호출될 때 마다 최대값을 갱신해줘야 한다. 예를 들어 해당 길의 최대 넓이가 6인데, 다른 길을 탐색했을 때 넓이가 7 이상이 나올 수 있기 때문에 count++ 이 아닌 count+1 로 인자를 넘겨줘서 최대값을 갱신해줘야 한다. 해당 길을 탐색했으면 다른 길도 탐색할 수 있게 방문처리를 false 로 돌려주어야 한다.

public static void dfs(int x, int y, int count) {
    alpha[map[y][x]-'A'] = true;
    ans = Math.max(ans, count);
    for(int k=0; k<4; k++) {
        int nx = x + dir[k][0];
        int ny = y + dir[k][1];

        if(nx<0 || ny<0|| nx>=M || ny>=N) continue;
        if(alpha[map[ny][nx]-'A']) continue;

        dfs(nx, ny, count+1);

        alpha[map[ny][nx]-'A'] = false;
    }
}

 

✅ 전체 코드

: )

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N,M,ans=0;
    static char[][] map;
    static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    static boolean[] alpha = new boolean[26];
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j);
            }
        }
    }

    public static void pro() throws IOException {
        dfs(0,0,1);
        System.out.println(ans);
    }

    public static void dfs(int x, int y, int count) {
        alpha[map[y][x]-'A'] = true;
        ans = Math.max(ans, count);
        for(int k=0; k<4; k++) {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];

            if(nx<0 || ny<0|| nx>=M || ny>=N) continue;
            if(alpha[map[ny][nx]-'A']) continue;

            dfs(nx, ny, count+1);

            alpha[map[ny][nx]-'A'] = false;
        }
    }
}