[백준] 1987번 - 알파벳 (Java)(○)

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

1987번: 알파벳

 

<문제 분석>

1. 세로 R, 가로 C로 된 맵이 있고, 대문자 알파벳으로 채워져 있음.

2. (1, 1)에 말이 있는데 상/하/좌/우로 움직일 수 있음. 그런데 이동한 칸의 알파벳은 이전 위치의 알파벳들과 달라야지 이동이 가능함. 

3. 칸을 지날 때 마다 알파벳을 저장하는 배열이 필요하고, 새 알파벳과 비교하는 함수가 필요함.

4. 방문배열도 당연히 필요함.

5. dfs함수 파라미터는 좌표를 넘겨주자.

 

<풀이 후기>

1. 방문한 칸의 알파벳을 ArrayList에 하나씩 추가를 해서 새 칸의 알파벳과 비교해서 true/false를 리턴하는 식으로 구현을 했는데 예제는 다 통과했지만 제출시 실패하는 케이스가 있었다.

2. visited 배열과 알파벳 비교 함수를 2개 운영하는 것이 비효율적이기도 하기에 대부분 visited 배열을 알파벳 숫자만큼 26개 만들어서 반복 된 것인지 하나로 확인하는 것 같다.

3. 그리고 dfs에서는 count를 전역변수로 하는게 아니라 dfs파라미터로 같이 넘겨서 중간중간 max값으로 저장하는 방식을 선호하는 것 같다.

 

 

<코드 구현 #1>

import java.util.*;

/*
[백준] 1987번 - 알파벳 (Java)
*/

public class Main {
    static int R, C;
    static char A[][];
    static boolean visited[][];
    static boolean alpha[];    

    void InputData() {
        Scanner in = new Scanner(System.in);
        R = in.nextInt();
        C = in.nextInt();
        A = new char[R][C];
        for (int i=0; i<R; i++) {
            String str = in.next();
            A[i] = str.toCharArray();         
        }
    }
    
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    void DFS(int x, int y, int count) {
        alpha[A[x][y]-'A'] = true;//알파벳 방문처리      
        max = Math.max(max, count);
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;//맵 범위 벗어나면
            if (alpha[A[nx][ny]-'A']) continue;//방문한 알파멧이면 스킵
            DFS(nx, ny, count+1);//다음칸에서 탐색 시작
            alpha[A[nx][ny]-'A'] = false;//다음 탐색을 위해 알파벳 방문처리 취소
        }
    }

    int max = 0;
    ArrayList<Character> list = new ArrayList<>();
    void Solve() {
        alpha = new boolean[26];
        DFS(0, 0, 1);
        System.out.println(max);
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

---

<코드구현 #2>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

/*
1. 같은 알파벳을 두번 지날 수 없으니 중복을 허용하지 않는 재귀함수이다.
  - 1차원 방문배열 사용(알파벳 26개)
2. 가지치기를 통한 재귀함수이니 백트래킹 알고리즘이다.
3. 가지치기
  - 맵 범위를 벗어나는 경우
  - 이미 방문한 알파벳인 경우
*/

public class Main {
    static int R, C;
    static boolean visited[];
    static char map[][];
    static int max_count = Integer.MIN_VALUE;
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};

    void DFS(int x, int y, int count) {
        int idx = map[x][y] - 'A';
        visited[idx] = true;
        max_count = Math.max(max_count, count);
        // 탐색시작
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 가지치기
            if (nx<0 || nx>=R || ny<0 || ny>=C) continue; // 범위 벗어나면 패스
            idx = map[nx][ny] - 'A';
            if (visited[idx]) continue; // 방문한 알파벳이면 패스
            // 탐색진행
            DFS(nx, ny, count+1);
            // 백트래킹으로 이전 노드로 복귀하면 다음을 위해 방문처리 취소
            visited[idx] = false;
            
        }
        
    }

	void Solve() {
        visited = new boolean[26];
        DFS(0, 0, 1);
        System.out.println(max_count);
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        for (int i=0; i<R; i++) {
            //st = new StringTokenizer(br.readLine());
            String str = br.readLine();
            for (int j=0; j<C; j++) {
                //map[i][j] = Integer.parseInt(st.nextToken());
                map[i][j] = str.charAt(j);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}