백준: 알파벳 - ( permuation 방문처리 )

🏆 문제 정보

문제 유형 : 백트랙킹 / DFS

문제 난이도 : 중

📌 문제

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

시작위치는 (0,0) . 알파벳은 지나갔었던 알파벳을 지날 수 없을 때, 지날 수 있는 최대 count를 구하라.

📌 생각

문제 자체는 일반적인 dfs이지만, 지나간 것을 어떻게 표시할 지가 문제였다.

 

첫번째로 생각했던 것은 List를 선언해서 지나갈 때마다 List에 담고, 매 재귀호출마다 해당 list와 paramter인 r,c를 확인해서 겹치면 return 하고, 겹치지 않으면 진행하는 식으로 하려고 했다.

 

여기에는 2가지 문제가 있었다.

 

⚡️1. 방문처리

permutation을 먼저 생각해보자.

 

해당 count=3 일 때,

v[i] = true

다음 함수 호출

v[i] = false 를 해주어야 한다.

 

v[i]=false 이 부분이 헷갈렸다. 함수가 끝나는 부분이니까 해줘도 의미없지 않나? 라고 생각이 들 수 있는데

현재 함수가 호출스택으로 관리되고 있다는 것을 생각해야 한다.

3이 호출됐을 때, 호출이 끝나고 3을 false처리를 해주지 않으면 다른 부분에서 3을 호출할 수 없다.

마찬가지로 저 부분에서 방문처리를 해주지 않았었는데, 해당 부분처럼 방문처리 false를 해주지 않으면 되돌아 갔을 때의 count가 되지 않는다.

 

⚡️2. 시간 초과

위의 방식대로 하면  매 호출마다 모든 list를 순회하면서 겹치는 지 확인하고, 또한 호출이 끝나면 다시 list 안에서 해당 character을 찾고 삭제해야 하므로 시간이 오래걸린다. 그래서 시간초과가 됐다.

 

다른 방법으로 알파벳 26개고 중복이 안되니까 boolean[] 배열 26개를 선언한다.

해당 알파벳 값에서 'A'를 빼면 0~26사이에 수가 형성되므로, boolean[] 과 1대1 대응시켜서 알파벳을 표현한다.

static boolean[] v = new boolean[26];
...
v[map[x][y]-'A']=true;
cnt++;

for(int i=0;i<4;i++){
    int nx = x+dx[i];
    int ny = y+dy[i];

    dfs(nx,ny,list,cnt);
}
v[map[x][y]-'A']=false;

📌 코드

package src.backjoon.알파벳;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class MainV2 {

    static int N,M;
    static char[][] map;
    static int count;

    static boolean[] v = new boolean[26];

    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("./src/backjoon/알파벳/input.txt"));

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        count=0;
        map = new char[N][M];

        for(int i=0;i<N;i++){
            char[] chars = sc.next().toCharArray();
            for(int j=0;j<M;j++){
                map[i][j] = chars[j];
            }
        }

        List<Character> list = new ArrayList<>();
        dfs(0,0,list,0);

        System.out.println(count);
    }

    private static void dfs(int x, int y, List<Character> list, int cnt) {
        if(isOut(x,y) || v[map[x][y]-'A']){
            count = Math.max(cnt,count);
            return ;
        }
        v[map[x][y]-'A']=true;
        cnt++;

        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];

            dfs(nx,ny,list,cnt);
        }
        v[map[x][y]-'A']=false;
    }

    static void print(){
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    static boolean checkAlphaIsRepeat(int r, int c, List<Character> list){
        for(Character character : list){
            if(map[r][c] == character) return true;
        }
        return false;
    }

    static boolean isOut(int nx, int ny){
        return nx<0 || nx>=N || ny <0 || ny >= M;
    }
}