[백준/1987] 알파벳 - JAVA

📌 문제

알고리즘 분류 : 그래프
난이도 : 골드4
출처 : 백준 - 알파벳

🦧 문제 풀이 접근

최대로 몇칸을 지날수 있는지 묻는 문제이므로 전체를 탐색해야한다. 메모리를 아끼기 위해 DFS방식과 Set을 사용했다.
지나간 모든 경로를 Set에 담고 중복체크를 했다.

💻 code

import java.util.*;
import java.io.*;

public class Main {
    static int maxSize;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        char board[][] = new char[R][C];
        for(int i=0;i<R;i++) {
            String line = br.readLine();
            for(int j=0;j<C;j++) {
                board[i][j] = line.charAt(j);
            }
        }
        Set<Character> set = new HashSet<>();
        DFS(0,0,set,board);
        System.out.println(maxSize);
    }

    static void DFS(int i, int j, Set<Character> set, char[][] board) {
        set.add(board[i][j]);
//        System.out.println(set);
        maxSize = Math.max(set.size(),maxSize);
        if(0<i) {
            if(!set.contains(board[i-1][j])) {
                DFS(i-1,j,set,board);
            }
        }
        if(0<j) {
            if(!set.contains(board[i][j-1])) {
                DFS(i,j-1,set,board);
            }
        }
        if(i<board.length-1) {
            if(!set.contains(board[i+1][j])) {
                DFS(i+1,j,set,board);
            }
        }
        if(j<board[0].length-1) {
            if(!set.contains(board[i][j+1])) {
                DFS(i,j+1,set,board);
            }
        }
        set.remove(board[i][j]);
    }
}

🥇 결과

🎓 느낀점

위 문제에서 한가지 중요한 부분이 있다.
보통 자바는 'Call by Value'로 값을 전달한다. 하지만 객체가 전달 될 때는 참조값(reference)의 복사본을 넘긴다.

즉, set 을 넘기면 set이라는 참조 변수 자체는 복사되지만, 복사된 참조가 가리키는 실제 Set 객체는 동일하다.

그렇기 때문에 위 코드에서 코드 마지막에 remove를 하였다.