백준 1987번 알파벳

문제 링크 : https://www.acmicpc.net/problem/1987

1. 보드에 적혀있는 알파벳 입력받고

2. ArrayList 생성

3. 0,0 부터 dfs로 탐색하면서 방문한 칸수 카운트 하고 그중 제일 큰 값 max_count 변수에 저장

이 과정에서 방문한 좌표의 char값을 ArrayList에 넣어주고, 다음좌표가 방문 가능한지 확인할때는 다음좌표의 char 값이 ArrayList에 있는지 확인하여 없는경우에만 방문하도록하였다.

4. max_count 출력

이렇게 풀었다. 재귀를 사용하여 가능한 경로를 모두 탐색하는 방법으로 풀었는데

아직 재귀를 이용한 완전탐색이 익숙치가 않아서 이렇게 짜는게 맞나 싶다.

좀이상하게 짜지 않았나 싶다.

불안하긴하지만 어쨌거나 '맞았습니다!!'를 받아서 블로그에 올린다.

다른사람 코드를 찾아서 비교해보고 수정하는건 내일 해야겠다.

아래는 소스코드이다.

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    static int r, c, max_count;
    static char[][] board;
    static boolean[][] visited;
    static int[] dy = { 0, 0, 1, -1 };
    static int[] dx = { 1, -1, 0, 0 };
    static ArrayList<Character> ar = new ArrayList<Character>();
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt();
        c = sc.nextInt();
        board = new char[r][c];
        visited = new boolean[r][c];
        
        for(int i=0; i<r; i++) {
            String input = sc.next();
            for(int j=0; j<c; j++) {
                board[i][j] = input.charAt(j);
            }
        }
        
        dfs(0,0,1);
        System.out.println(max_count);
    }
    
    
    static public void dfs(int y, int x, int count) {
        ar.add(board[y][x]);
        visited[y][x] = true;
        max_count = Math.max(count, max_count);
        
        for(int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            boolean flag = false;
 
            if ( ny<0 || nx<0 || ny>=r || nx>=c ) continue;
            if ( visited[ny][nx] == true ) continue;
            for(int j=0; j<ar.size(); j++) {
                if(ar.get(j) == board[ny][nx]) {
                    flag = true;
                    break;
                }
            }
            if( flag == true ) continue;
 
            dfs(ny, nx, count+1);
        }
 
        ar.remove(ar.size()-1);
        visited[y][x] = false;
    }
    
}