SWEA [D4] 7699번: 수지의 수지 맞는 여행

숮이의 숮이 맞는 여행

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

시간 안잼

TreeSet사용!! 실행시간 줄여야됨. 최적화 공부 해야한다~~~

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.TreeSet;
 
//수지의 수지 맞는 여행
public class Solution {
    static int R, C, max;
    static char[][] map;
    static boolean[][] visited;
    static TreeSet<Character> check;
 
    static int[] dx = {-1, 0, 1, 0}, dy= {0, 1, 0, -1};
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int tc = Integer.parseInt(str);
         
         
        for (int testCase = 1; testCase <= tc; testCase++) {
            str = br.readLine();
            String[] sarr = str.split(" ");
            check = new TreeSet<>();
             
            max = Integer.MIN_VALUE;
            R = Integer.parseInt(sarr[0]);
            C = Integer.parseInt(sarr[1]);
            map = new char [R][C]; //0인덱스 사용 X
            visited = new boolean[R][C];
 
            for (int r = 0; r < R; r++) {
                map[r] = br.readLine().toCharArray();
//              System.out.println(br.readLine().toCharArray().length);
            }
             
            check.add(map[0][0]);
            visited[0][0] = true;
            travel(0,0);
            System.out.println("#"+testCase+" "+max);
        }//end of testCase
         
         
         
    }//end of main
    public static void travel(int x, int y) {
        for (int d = 0; d < 4; d++) {
            int tmpx = x+dx[d];
            int tmpy = y+dy[d];
            if(isIn(tmpx, tmpy) && !check.contains(map[tmpx][tmpy]) && !visited[tmpx][tmpy]) {
                check.add(map[tmpx][tmpy]);
                visited[tmpx][tmpy] = true;
                travel(tmpx, tmpy);
                check.remove(map[tmpx][tmpy]);
                visited[tmpx][tmpy] = false;
            }
        }
        if(check.size()>max) max = check.size();
    }//end of travel
     
    public static boolean isIn(int x, int y) {
        if(x>=0 && y>=0 && x<R && y<C) return true;
        else return false;
    }
}//end of class
/*
3
2 4
CAAB
ADCB
3 6
HFDFFB
AJHGDH
DGAGEH
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH
*/