알파벳(백트래킹) - 백준 골드4

- 알파벳 문제

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

 

- 풀이

걸린 시간 : 2시간 20분

import java.io.*;
import java.util.*;
public class Main {

    public static int M, N;
    public static int countAll = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        if(M == 1 && N == 1){
            bw.write(String.valueOf(1));
            br.close();
            bw.close();
            return;
        }
        String[] graph = new String[M];
        HashSet<Character> set = new HashSet<>();
        for(int i = 0; i < M; i++){
            graph[i] = br.readLine();
        }

        dfs(graph, set, 0, 0, 0);
        bw.write(String.valueOf(countAll));
        br.close();
        bw.close();
    }

    public static void dfs(String[] graph, HashSet<Character> set, int y, int x, int count){
        if(x < 0 || x >= N || y < 0 || y >= M){
            return;
        }
        if(set.contains(graph[y].charAt(x))){
            if(countAll < count) countAll = count;
            return;
        }
        set.add(graph[y].charAt(x));
        count++;
        dfs(graph, set, y + 1, x, count);
        dfs(graph, set, y - 1, x, count);
        dfs(graph, set, y, x + 1, count);
        dfs(graph, set, y, x - 1, count);
        
        // 중요!!!!
        set.remove(graph[y].charAt(x));
    }
}

이번 문제는 백트래킹이다.

백트래킹은 DFS에 변형을 더한 유형이라 넘어가게 되었다.

 

이 문제는 비교적 이해는 잘갔다.

그냥 각각의 경로에 따른 알파벳 모음을 유지하며 DFS를 시도하면 되기 때문이다.

 

하지만 백준은 그렇게 쉽게 넘어가지 않았다...

메모리 초과, 시간 초과를 내뿜으며 골드4 문제임을 다시금 깨닫게 해주었다.

 

시간초과를 없앨 수 있는 방법을 모조리 생각했지만, 뭐가 되지 않았다.

그렇게 2시간이 지났을 즘이었을까,

코테 파트너분과 나는 포기 상태에 이르렀다.

코테 파트너분이 GPT에게 접근 방식을 물어보니,

 

하나의 Set으로 관리해야 하며, 해당 자리의 값을 Set에서 지워줘야 한단다.

하나의 Set으로 관리하는 건 진작에 알고 있었지만, 구현 방법이 도저히 생각이 안났다.

한 15분을 고민하다가 dfs가 전부 돌고 난 후 Set.remove()를 사용해줘봤는데

드라마틱하게 정답이 되고야 말았다.

 

단순히

set.remove(graph[y].charAt(x));

이 한줄만 추가해줬는데 말이다...

왜일까 고민해보았다.

 

이 코드는 절대 모든 dfs가 실행될때까지 실행되지 않는 함수이다.

그렇다면 이 코드는 상하좌우 모두에서 퇴자를 맞은 어떠한 한 경로의 끝이라는 부분이다.

그럼 우리는 countAll을 업데이트해준 후,

다시 뒤로 돌아가야 한다.

 

그때! 우리는 Set에서 되돌아 가는 곳까지 해당 인덱스의 알파벳을 Set에서 삭제를 해줘야 한다.

왜냐하면 우리는 하나의 Set으로 관리해야만 하니까..!

 

모든 DFS가 끝난 인덱스의 알파벳을 Set에서 제거하며 하나하나 뒤로 가다보면 모든 DFS가 안끝난 자리가 있을 것이고,

해당 부분부터 다시 Set에 추가하며 나아간다.

이해하셨다면 다행입니다^^

 

이렇게 이 문제가 해결되었다.

정말 저 코드 하나에 2시간을 썼다는게 무섭지만, 백트래킹에 대해 좀 더 알게되었다.

하나의 Set으로 DFS가 유지되는 방법 또한 알게 되었으니

성장할 일밖에 더 있겠는가?

 

우리는 "코딩왕"이 될 것이니까.