[DFS] BOJ 1987번, 알파벳(JAVA)

---

문제풀이

 

1. 알파벳이 나왔는지 확인할 수 있는 배열을 만들어서 해당 문자를 아직 방문하지 않았을 경우에만 방문하는

방법을 사용한다.

 

2. dfs 매개변수로 현재까지 나온 문자열을 전달하여 이 문자열에 포함되어 있지않으면 다음 문자를 추가해 주는 방식

이때 s.contains(Chracter.toString(arr[ny][nx]))  이러한 방법을 이용하는데 이 contains 라는 메소드가 배열 길이 만큼 시간이 걸린다. 이걸 dfs로 돌리면 시간이 매우 오래 걸리지만 통과는 하는 듯 싶다.

 

두가지 방법을 모두 한번씩 확인해보고 왜 1번 방법이 더 빠른지 생각해보면 좋을듯 싶다.

 

---

소스코드1

import java.util.*;
import java.io.*;
class Main{
    static int n,m;
    static int[][] arr;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int ans;
    static boolean[] visited = new boolean[26];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        for(int i=0;i<n;i++)
        {
            String input = br.readLine();
            for(int j=0;j<m;j++)
            {
                arr[i][j] = input.charAt(j) - 'A';
            }
        }
        visited[arr[0][0]] = true;
        dfs(0, 0, 1);
        
        System.out.println(ans);
    }
    public static void dfs(int y, int x, int count)
    {
        ans = Math.max(ans, count);
        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= 0 && nx >= 0 && ny < n && nx < m)
            {
                if(!visited[arr[ny][nx]])
                {
                    visited[arr[ny][nx]] = true;
                    dfs(ny,nx,count+1);
                    visited[arr[ny][nx]] = false;
                }
            }
        }
    }
}

소스코드2

import java.util.*;
import java.io.*;
class Main{
    static int n,m;
    static char[][] arr;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int ans;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        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 input = br.readLine();
            for(int j=0;j<m;j++)
            {
                arr[i][j] = input.charAt(j);
            }
        }
        dfs(0,0, Character.toString(arr[0][0]));
        
        System.out.println(ans);
    }
    public static void dfs(int y, int x, String s)
    {
        ans = Math.max(ans, s.length());
        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny>=0 && nx >=0 && ny < n && nx < m)
            {
                if(!s.contains(Character.toString(arr[ny][nx])))
                {
                    dfs(ny,nx,s+arr[ny][nx]);
                }
            }
        }
    }
}