[BOJ - JAVA] 1987 - 알파벳 (DFS)

# 주소

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

1987번: 알파벳

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int n,m;
    static char[][] arr;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static int ans = 0;
    static HashSet<Character> hash = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new char[n][m];
        for(int i = 0; i < n; i++){
            String str = br.readLine();
            for(int j = 0; j < m; j++){
                arr[i][j] = str.charAt(j);
            }
        }
        hash.add(arr[0][0]);
        dfs(0,0,1);
        System.out.print(ans);
    }
    public static void dfs(int x, int y, int count){
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                continue;
            }
            if(hash.contains(arr[nx][ny])){
                ans = Math.max(ans,count);
            }
            else{
                hash.add(arr[nx][ny]);
                dfs(nx,ny,count+1);
                hash.remove(arr[nx][ny]);
            }
        }
    }
}

일반적인 Queue로 풀려고 했으나, DFS 문제이기에 계속해서 고민했습니다.

아무래도 자료구조를 활용하는게 전 좋았기 때문에, 중복을 허용하지 않는 자료구조... 바로 HashSet을 사용하면 어떨까?

라고 생각했고 실제로 HashSet을 통해 손쉽게 구현이 가능했습니다.

기본적으로 HashSet은 자료에 인덱스나 순서를 부여하지 않고 관리하는 것이 특징입니다.

따라서 자료를 넣고 찾는데 엄청 빠르기도 하지만 get()등의 메서드를 이용하여 자료를 가지고 나올 수 없습니다.

하지만 이  Hashset을 사용하는 가장 큰 이유는 중복된 자료를 허용하지 않기 때문에, 상황에 맞게 적절하게 사용하면 굉장히 요긴하게 쓸 수 있겠습니다.

만약 Hashset을 순서대로 쭉 출력하고 싶다면, 음... Iterator를 사용하는 방법이 있겠네요.

Iterator를 통해, 자료구조를 쭉 돌리면 되겠지요.

HashSet<Integer> list = new HashSet<>();
Iterator<Integer> iter = list.Iterator();
while(iter.hasNext()){
	int next = iter.next();
    System.out.println(next);
}

이런식으로 말이지요.

자 그럼 Hashset을 어떻게 활용할 수 있을지 한 번 살펴보죠.

맨 먼저 arr에 문자들을 각각 분리해서 삽입합니다.

이후 static으로 선언했던 hash에 arr[0][0]을 삽입합니다.

그리고 dfs(0,0,1)을 실행하는데, 처음 인덱스인 0,0에서의 값도 포함한다 했으므로 출력이 되는 최소값은 1입니다.

public static void dfs(int x, int y, int count){
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                continue;
            }
            if(hash.contains(arr[nx][ny])){
                ans = Math.max(ans,count);
            }
            else{
                hash.add(arr[nx][ny]);
                dfs(nx,ny,count+1);
                hash.remove(arr[nx][ny]);
            }
        }
    }

dfs문을 보시겠습니다.

여기에선 visit의 구현이 따로 필요 없습니다.

왜냐하면 방문했던 값이 중복된 hash값을 가지고 있으면 그건 돌아가야 하기 때문에.. visit은 필요없는것입니다.

그러므로 for문을 이용하여 새로 배정받는 인덱스의 위치인 nx,ny를 신경써주시고, 만약 이것들이 음수가 되거나 n 또는 m보다 커지면 continue를 시켜 연산하지 않게 합니다.

그리고 만약 hash.contains[arr[mx][ny]] -> hash가 arr[nx][ny]를 가지고 있다면

ans는 ans와 count 중 큰 값을 저장합니다.

그리고 hash에 arr값이 없다면, hash에는 새로운 arr값을 삽입하고 dfs에 (nx,ny,count+1)한 값을 넣어줍니다.

그리고 쭉 dfs문을 돌리면서 arr값이 hash에 없으면 계속해서 방문하는 모양새를 보여줄 것입니다.

그러나, 또다시 가지고 있던 인덱스의 값을 마주했을 때 dfs는 그 값을 제거하고 리턴해야 할 것입니다.

그러니까, 만약 들고 있던 값을 내가 들고 있었는데, 이걸 또 벽에서 마주쳤으니 당연히 아 여긴 아니구나 하고 선회해야 겠지요?

그래서 visit값이 필요 없고 dfs만으로도 구현이 가능한 것입니다.

만약 이해가 어려우면 생각을 해봅시다.

 

여러분이 dfs문을 쭉 돌리면서 hash에 없던 값들을 계속 추가하며 미로를 탐방하고 있습니다.

그런데, 예전에 왔던 길을 오면 사람 심리가 어떤가요? 아 잘못 왔구나 하고 돌아가겠지요.

여기서도 마찬가지입니다. dfs는 바보이기 때문에, 아니 컴퓨터는 근본적으로 바보이기 때문에 dfs가 재귀형태로 계속해서 실행이 되다가 만약 더이상 dfs문이 실행되지 않는 (hash에 가지고 있던 값을 또 만났을 경우) 이 때는 제일 밑의 hash.remove(arr[nx][ny])가 실행되어, "아 잘못 왔구나 기록에서 지워야지" 하고 지우게 되는 것입니다.

이해가셨나요?

감사합니다.