[백준(Python/Java)] 1987_알파벳 - DFS

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

1987번: 알파벳

 

깊이 우선 탐색(DFS)을 통해 가장 긴 알파벳을 찾는 문제였습니다.

 

기존에 풀었던 많은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)를 문제에서는 방문한 곳을 true로 체크하여 재방문을 하지 않도록 알고리즘을 설계했습니다.

 

하지만 이 문제에서는 깊이 우선 탐색을 하여 방문한 곳들이 최적해가 되지 않을 때, 다시 그 곳들의 방문 여부를 false로 복원하여 다음 탐색에서 방문할 수 있도록 해야 합니다.

 

말이 거창한 것 같은데 사실 DFS를 통해 "모든 가능한 경로"를 탐색해야 한다는 뜻입니다.

 

따라서 아래 코드에서 dfs() 메서드를 재귀적으로 호출할 때, 재귀 호출이 끝난 후에는 visited 배열과 alphabet 배열을 dfs 재귀 호출 이전으로 돌려주는 코드만 추가해주면 완전 탐색을 할 수 있습니다.

 

파이썬과 자바 코드는 완전히 동일합니다.

 

[풀이 - 파이썬]

import sys
input = sys.stdin.readline

def dfs(x, y, alphabet, visited, count):
    global length

    # 해당 위치 방문 체크, 알파벳 포함 체크
    visited[x][y] = True
    alphabet[ord(graph[x][y])] = True
    count += 1
    if count > length:
        length = count

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < r and 0 <= ny < c:
            nextString = graph[nx][ny]
            # 현재 알파벳에 포함되지 않은 알파벳이라면
            if not alphabet[ord(nextString)]:
                if not visited[nx][ny]:
                    dfs(nx, ny, alphabet, visited, count)

                    # 탐색했던 위치들과 알파벳을 복원
                    visited[nx][ny] = False
                    alphabet[ord(graph[nx][ny])] = False

        

r, c = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(r)]
dx, dy = [1,-1,0,0], [0,0,1,-1]
length = 0
visited = [[False] * c for _ in range(r)]
alphabet = [False] * 100
dfs(0,0,alphabet,visited, 0)
print(length)

[풀이 - 자바]

package PS;

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

public class B_1987 {
    static int r, c;
    static char[][] graph;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static int length;
    static boolean[][] visited;
    static boolean[] alphabet;

    public static boolean OOB(int x, int y, int r, int c){
        return 0 <= x && x < r && 0 <= y && y < c;
    }

    public static void dfs(int x, int y, boolean[] alphabet, boolean[][] visited, int count){
        // 해당 위치 방문 체크, 알파벳 포함 체크
        visited[x][y] = true;
        alphabet[(int)graph[x][y]] = true;
        count++;

        if(count > length){
            length = count;
        }

        for(int dir = 0; dir < 4; dir++){
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if(OOB(nx, ny, r, c)){
                char nextChar = graph[nx][ny];
                // 현재 알파벳에 포함되지 않은 알파벳이라면
                if(!alphabet[(int)nextChar]){
                    if(!visited[nx][ny]){
                        dfs(nx, ny, alphabet, visited, count);

                        // 탐색했던 위치들과 알파벳을 복원
                        visited[nx][ny] = false;
                        alphabet[(int)graph[nx][ny]] = false;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        // 입력받기
        graph = new char[r][c];
        for(int i = 0; i < r; i++)
            graph[i] = br.readLine().toCharArray();
        visited = new boolean[r][c];
        alphabet = new boolean[100];

        // DFS 수행 후 결과 출력
        dfs(0,0,alphabet,visited, 0);
        System.out.println(length);
    }

}