[문제 풀이] 백준 1987번 알파벳 JAVA

문제

  문제접근 방법   

해당 문제는 R*C 칸의 보드가 존재하고 각각의 칸마다 알파벳이 들어있다고 할 때

상하좌우로 움직여 알파벳이 중복되지 않고 지날 수 있는 최대 길이를 구하는 프로그램을 작성하는 문제이다.

처음 문제를 읽고 dfs로 접근하여 문제를 해결해야겠다고 생각했다. 하지만 일반적인 dfs에서 visited를 통해

방문처리를 하는데 반면 해당 문제에서는 그렇게 처리할 경우 모든 경우를 고려하지 못하게 되는 상황이 발생할 수도 있겠다고 생각했다. 그래서 방문처리에 대해서 고민하다가 visited로 알파벳 수만큼 선언하고 관리할지 Set을 활용한 중복 관리로 문제를 해결할지를 고민한 결과 Set을 활용한 방법이 접근이 더 수월할 것이라 판단 아래와 같이 코드를 작성하였다. 

< 초기 코드  >

import java.util.*;

public class Main{
    public static boolean visited[][];
    public static char map[][];
    public static int maxLen=0;
    public static Set<Character> set=new HashSet<>();
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int r=s.nextInt();
        int c=s.nextInt();
        map=new char[r+1][c+1];
        for(int i=1;i<=r;i++){
            String str=s.next();
            for(int j=1;j<=c;j++){
                map[i][j]=str.charAt(j-1);
            }
        }
        
        set.add(map[1][1]);
        dfs(1,1);
        System.out.print(maxLen);
    }
    public static void dfs(int x,int y){
        
        
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        
        
        for(int i=0;i<4;i++){
            int nx=dx[i]+x;
            int ny=dy[i]+y;
            
            if(nx>0&&ny>0&&nx<map.length&&ny<map[1].length){
                int size=set.size();
                set.add(map[nx][ny]);
                if(size!=set.size()){
                    maxLen=maxLen>set.size()?maxLen:set.size();
                    dfs(nx,ny);
                    set.remove(map[nx][ny]);
                }
                
            }
            
        }
    }
}

위에서 언급하였듯이 여러 시행착오와 고민 끝에 Set을 통해 중복관리를 한다면 방문처리도 당연하게 따라오는 부분이라 Set을 

활용하여 코드를 작성하였다. 

다른 코드들은 일반 dfs와 구조가 같기 때문에 본인이 생각하는 핵심만 설명하고 넘어가도록 하겠다.

여기서 핵심은 set을 어떻세 중복관리를 하는지이다. Set은 같은 숫자가 들어오면 자동으로 중복된 값을 제외시킨다. 그래서 1,2,3이 들어있던 set에 1을 추가로 넣는다고 해도 1,2,3,1이 되는 것이 아니라 중복된 수가 제외된 1,2,3 그대로 남게 된다.

이를 활용하여 set.size()를 먼저 변수에 저장해 두고 set.add()를 한다. 

이때 set.size()를 저장한 변수와 set.add를 한 이후의 길이를 비교했을 때 같다면 중복된 값이 들어간 것이고

아니라면 중복되지 않은 값이 들어간 것이다. 또 이를 통해 방문처리도 가능한 이유는 중복된 값이 허용되지 않기 때문에

Set에 들어있는 값은 이미 다녀온 곳인 것을 알 수 있기 때문에 이미 다녀간 곳은 갈 수 없게 되는 것이다. 

하지만 해당 코드는 80%~ 정도에서 틀렸다는 판정을 받았다.

여기서 잡기술하나 알려주자면 80% 정도에서 틀렸다면 코드 전체가 틀렸을 수도 있지만

100에서 80은 맞았기 때문에 조건 몇 개를 고려하지 못해 틀린 것일 수도 있다.

그래서 이 정도 맞았는데 틀렸다면 본인의 경우 문제를 다시 한번 읽어보고 코드를 자세하게 다시 본다.

그 결과 해당 문제 같은 경우 maxLen의 위치가 문제여서 처음 값이 최대 값일 수도 있는 경우를 고려하지 못했던 것을 확인

아래와 같이 코드를 수정하였다. 

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static boolean visited[][];
    public static char map[][];
    public static int maxLen=0;
    public static Set<Character> set=new HashSet<>();
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int r=s.nextInt();
        int c=s.nextInt();
        map=new char[r+1][c+1];
        for(int i=1;i<=r;i++){
            String str=s.next();
            for(int j=1;j<=c;j++){
                map[i][j]=str.charAt(j-1);
            }
        }
        
        set.add(map[1][1]);
        dfs(1,1);
        System.out.print(maxLen);
    }
    public static void dfs(int x,int y){
        
        
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        
        maxLen=maxLen>set.size()?maxLen:set.size();
        for(int i=0;i<4;i++){
            int nx=dx[i]+x;
            int ny=dy[i]+y;
            
            if(nx>0&&ny>0&&nx<map.length&&ny<map[1].length){
                int size=set.size();
                set.add(map[nx][ny]);
                if(size!=set.size()){
                    
                    dfs(nx,ny);
                    set.remove(map[nx][ny]);
                }
                
            }
            
        }
    }
}

maxLen값 경신을 dfs가 호출되자마가 해줌으로써 모든 수를 고려할 수 있게 되었다.

  마무리  

해당 문제는 일반적인 방문처리가 아닌 하나의 조건이 더 있어서 굉장히 오래 생각했고 어렵게 느껴졌던 문제이다.

본인은 Set을 통해 문제를 접근하고 해결하였지만 다른 방법도 있을 것으로 예상되고 꼭 한 번 풀어보면 좋겠다.

  추가 코드 분석 및 풀이  

위에서도 언급하였듯이 해당 문제는 풀이가 여러개일 것으로 생각되어 여러 코드를 분석해 본 결과 2가지 정도 방식으로 

더 풀어보고 분석해보았다.

첫 번째 방식은 boolean [26] 배열을 사용하는 방식으로 처음에 문제를 이렇게 접근하려고 했지만 

boolean이 아닌 int형으로 카운트하는 방식으로 접근해 어려워 포기했었다. 하지만 boolean으로 접근하면

풀이가 아래처럼 어렵지 않게 접근 가능했다. 하지만 이 모든 것이 

위에서 이미 다른 dfs문제들과는 다른 방문처리를 해보았기 때문에 풀이가 가능한 것임을 느끼었다.

 

< 추가 코드 ver boolean [26] 배열  >

import java.util.*;

public class Main{
    public static boolean visited[];
    public static char map[][];
    public static int maxLen=0;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int r=s.nextInt();
        int c=s.nextInt();
        map=new char[r+1][c+1];
        visited=new boolean[26];
        for(int i=1;i<=r;i++){
            String str=s.next();
            for(int j=1;j<=c;j++){
                map[i][j]=str.charAt(j-1);
            }
        }
        
        visited[map[1][1]-65]=true;
        dfs(1,1,1);
        System.out.print(maxLen);
    }
    public static void dfs(int x,int y,int cnt){
        
        
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        
        maxLen=maxLen>cnt?maxLen:cnt;
        for(int i=0;i<4;i++){
            int nx=dx[i]+x;
            int ny=dy[i]+y;
            
            if(nx>0&&ny>0&&nx<map.length&&ny<map[1].length){
                
                if(!visited[map[nx][ny]-65]){
                    visited[map[nx][ny]-65]=true;
                    dfs(nx,ny,cnt+1);
                    visited[map[nx][ny]-65]=false;
                }
                
            }
            
        }
    }
}

위에서도 언급하였듯이 이미 위에서 set으로 풀어보았기 때문에 이해하기 쉬웠던 것이지 이런 접근자체가 처음 하면 어려울 것이라 생각된다. 해당 코드는 위의 최종 코드와 모든 부분이 같지만 딱 한 부분만이 다르다. 

바로 중복처리, 방문처리를 해주는 부분이다. 최종코드에서는 Set을 활용하였지만 해당 코드에서는 배열과 아스키코드를 활용하였다. 자바에서 int형과 char형은 매우 밀접한 관계를 가진다고 표현할 수 있는데 왜냐하면 char는 내부적으로 숫자(정수)로 표현되고

16비트를 가지고 여기서 int는 32비트 정수형이므로 char 값은 int로 자동 형변환(promotion) 됩니 때문에 이와 같이 표현할 수 있습니다. 즉 A-65를 int형으로 형변환되면 A는 내부적으로 정수이기 때문에 계산이 가능해지고 0으로 표현할 수 있는 것입니다.

 

< 추가 코드 ver  bitmask   >

추후 업데이트 예정

 

 참고 자료