#유형:탐색, 순열, DFS

# aabbbaa 같은 경우 abababa

# abc => abc acb bac bca cab cba 같이 순열을 만들어서 행운의 문자열인지 체크하면 된다. 

# dfs, 순열의 개념을 알고있었다면 그렇게 어렵지 않은 문제. 시간초과만 주의해주면 된다. 맨 처음에는 순열을 호출할때마다 조건문으로 검사하거나 순열의 파라미터를 String이나 리스트로 넘겼는데, 시간초과가 났다. 그래서 우선 길이에 맞는 순열을 만들때마다 조건문으로 행운의 문자열인지 체크해줘서 count++하면 된다. 이 때 리스트의 첫 번째인덱스부터 다음 인덱스와 같으면 false를 리턴하게 하면 된다.

그리고, 이렇게 짜면 문제점이 중복값이 나온다. aabbbaa 같은 경우에 a가 4개여서 순서가 바뀌어서 중복이 발생하는데, 이 때 팩토리얼로 나눠주면 중복을 없앨수있다.

 

순열 https://ukyonge.tistory.com/16?category=870876

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package bj;
 
 
public class p1342 {
    static int result=0;
    static String str;
    static ArrayList<Character> arrList = new ArrayList<>();
    static int al[] = new int[26];
    static char arr[] = new char[10];
    static boolean visit[] = new boolean[10];
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        
        for(int i=0; i<str.length(); i++) {
            al[str.charAt(i)-'a']++;
        }
        
        permutation(0);
        
        for(int i=0; i<26; i++) {
            if(al[i] > 1) {
                result /= factorial(al[i]);
            }
        }
        System.out.println(result);
    }
    public static boolean check() {
        
        for(int i=0; i<arrList.size()-1; i++) {
            if(arrList.get(i)==arrList.get(i+1))
                return false;
        }
        return true;
    }
    public static int factorial(int N) {
        if(N==1)
            return 1;
        
        return N*factorial(N-1);
    }
    public static void permutation(int count) {
        if(count == str.length()) {
            if(check()) {
                result++;
                return;
            }    
        }
        for(int i=0; i<str.length(); i++) {
            if(!visit[i]) {
                visit[i] = true;
                arrList.add(str.charAt(i));
                permutation(count+1);
                arrList.remove(arrList.size()-1);
                visit[i] = false;
            }
        }
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'백준' 카테고리의 다른 글

#백준_3190 뱀 - Java 자바  (0) 2020.02.02
#백준_1120 문자열 - Java 자바  (0) 2020.01.31
#백준_1022 소용돌이 예쁘게 출력하기 - Java 자바  (0) 2020.01.31
#백준_1405 미친 로봇 - Java 자바  (0) 2020.01.30
#백준_1057 토너먼트 - Java  (0) 2020.01.29

#유형 : 시뮬레이션

# 규칙을 찾는데 시간이 오래 걸렸고, 메모리 생각안하고 전체 소용돌이 출력하다가 메모리 초과가 났다. 따라서 소용돌이 중 범위에 해당하는 부분만 구해서 출력을 했더니 해결하였다.

 

소용돌이 규칙

1. 시작 방향은 오른쪽, 진행 방향은 오른쪽->위쪽->왼쪽->아래->오른쪽.. 반복이다

2. 회전을 두 번 할 때마다 전진하는 길이가 늘어난다. 결국은 오른쪽과 왼쪽으로 이동 시에 길이가 1개씩 늘어나는 셈이다.

3. 소용돌이 전체를 구하면 메모리 초과가 난다. 따라서 구간에 속하는 부분만 구한다.

4. 띄어쓰기는 가장 큰 숫자의 자리수에서 해당하는 숫자의 자리수의 차이를 구한 만큼 공백을 더해줘서 출력한다.

 

예시)

1(오른쪽,1칸)->2(위쪽,1칸)->3(왼쪽,2칸)->5(아래쪽,2칸)->7(오른쪽,3칸)->10(위쪽,3칸)->13(왼쪽,4칸)->17...

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package bj;
 
 
public class p1022 {
    static int arr[][] = new int[50][5];
    static int moveX[] = {1,0,-1,0};
    static int moveY[] = {0,-1,0,1};
    static int r1,r2,c1,c2;
    static int maxCount, maxValue=0;
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        r1 = Integer.parseInt(st.nextToken());
        c1 = Integer.parseInt(st.nextToken());
        r2 = Integer.parseInt(st.nextToken());
        c2 = Integer.parseInt(st.nextToken());
        
        maxCount = (Math.abs(r1-r2)+1) * (Math.abs(c1-c2)+1);
        
        solve();
        
        int space = len(maxValue);
        for(int i=0; i<=Math.abs(r1-r2); i++) {
            for(int j=0; j<=Math.abs(c1-c2); j++) {
                int currentSpace = len(arr[i][j]);
                for(int k=0; k<space-currentSpace; k++)
                    System.out.print(" ");
                System.out.print(arr[i][j]+" ");
            }System.out.println();
        }
        
//        for(int i=0; i<50; i++) {
//            for(int j=0; j<5; j++) {
//                System.out.print(arr[i][j]+" ");
//            }System.out.println();
//        }
        
    }
    public static int len(int value) {
        int result = 0;
        while(value>=10) {
            result++;
            value/=10;
        }
        return result;
    }
    
    public static void solve() {
        int x = 0,y = 0;
        int val = 1;
        int cnt = 1;
        int d=0;
        int len=0;
        boolean visit=false;
        
        if(r1<=y && y<=r2 && c1<=x && x<=c2) {
            arr[y-r1][x-c1] = val++;
            cnt++;
            visit = true;
        }
        if(!visit)
            val++;
        
        while(cnt<=maxCount) {
            d%=4;
            if(d==0 || d==2)
                len++;
            for(int i=0; i<len; i++) {
                x += moveX[d];
                y += moveY[d];
                if(r1<=y && y<=r2 && c1<=x && x<=c2) {
                    arr[y-r1][x-c1] = val;
                    maxValue = Math.max(maxValue, val);
                    cnt++;
                }
                val++;
            }
            d++;
        }
        
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'백준' 카테고리의 다른 글

#백준_1120 문자열 - Java 자바  (0) 2020.01.31
#백준_1342 행운의 문자열 - Java 자바  (0) 2020.01.31
#백준_1405 미친 로봇 - Java 자바  (0) 2020.01.30
#백준_1057 토너먼트 - Java  (0) 2020.01.29
#백준_1019 책 페이지 - Java  (0) 2020.01.29

# 유형 : 탐색 

# 난이도 : Gold V

# 쉽게 볼 수 있는 DFS 문제.. 동서남북 방문 안한 곳을 갈 때마다 확률 값을 곱해줘서 매개변수로 넘겨주면서 카운트와 이동 횟수가 일치할 때 합을 해주면 된다. 아무리 풀어도 틀리길래.. 잘 못 풀은 줄 알았는데 확률값이 동/서/남/북 순서로 들어오는데 이걸 안 보고 계속 왜 틀리지 생각했다.. 문제를 꼼꼼히 읽자....

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1405 {
    static int N;
    static int prob[] = new int[4];
    static boolean visit[][]=new boolean[30][30];
    static int moveX[] = {1,-1,0,0};
    static int moveY[] = {0,0,1,-1};
    static double result = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for(int i=0; i<4; i++) {
            prob[i] = Integer.parseInt(st.nextToken());
        }
        visit[15][15]=true;
        dfs(15,15,0,1.0);
        System.out.println(String.format("%.10f", result));
    }
    
    public static void dfs(int i, int j, int cnt, double val) {
        
        if(cnt == N) {
            result += val;
            return;
        }
        
        
        
        for(int d=0; d<4; d++) {
            int newX = j + moveX[d];
            int newY = i + moveY[d];
            if(!visit[newY][newX]) {
                visit[newY][newX]=true;
                dfs(newY, newX, cnt+1, val*0.01*prob[d]);
                visit[newY][newX] = false;
            }
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1342 행운의 문자열 - Java 자바  (0) 2020.01.31
#백준_1022 소용돌이 예쁘게 출력하기 - Java 자바  (0) 2020.01.31
#백준_1057 토너먼트 - Java  (0) 2020.01.29
#백준_1019 책 페이지 - Java  (0) 2020.01.29
#백준_2143 두 배열의 합 - Java  (0) 2020.01.28

#유형 : 시뮬레이션 

# 토너먼트가 진행할때마다 홀수인 경우에는 num/2 + 1 짝수일 경우에는 num/2 로 진행된다. 그러면 타겟끼리 같은 그룹인지 어떻게 체크하냐면 예를들어 1 2 3 이런 경우에 +1하고 /2를 해주면 그룹핑이 가능해진다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1057 {
    static int N,A,B;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        int cnt = 1;
        while(true) {
            int rs1 = solve(A);
            int rs2 = solve(B);
            
            if(rs1==rs2)
                break;
            
            if(A%2==0)
                A/=2;
            else if(A%2==1) {
                A/=2;
                A++;
            }
            if(B%2==0)
                B/=2;
            else if(B%2==1) {
                B/=2;
                B++;
            }
            
            cnt++;
        }
        System.out.println(cnt);
    }
    public static int solve(int num) {
        num+=1;
        return num/2;
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1022 소용돌이 예쁘게 출력하기 - Java 자바  (0) 2020.01.31
#백준_1405 미친 로봇 - Java 자바  (0) 2020.01.30
#백준_1019 책 페이지 - Java  (0) 2020.01.29
#백준_2143 두 배열의 합 - Java  (0) 2020.01.28
#백준_6603 로또 - Java  (0) 2020.01.27

#유형 : 탐색

# 많이 어려웠던 문제... 풀다가 메모리초과, 시간초과 때문에 도저히 모르겠어서 백준님 슬라이드를 통해 이해하고 풀었다.

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019

 

우선 시작 숫자와 마지막 숫자의 일의 자리수를 0과 9로 맞춘다.

쉽게 설명하자면 만약 10에서 29사이의 사용된 0~9 숫자를 구하면 다음과 같다.

 

10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

일의 자리만 보면 된다. 0~9사이가 2개씩 나왔다. (2-1+1)*1 => 2

 

다른 예로, 일의 자리 기준으로 생각해보자.  1350 ~ 8739 는 (873-135+1)*1 . 따라서 arr[0~9] 에는 873-135+1 를 더할수 있다.

그 다음에는 십의 자리를 구해보면 된다. 각 숫자를 10으로 나눠준다. 135 ~ 873 를 각각  ++, -- 를 통해 140 ~ 869로 만들어준다.

140 ~ 869 는 86 - 14 + 1 을 더할수 있다. 이 때 지금 구하고 있는 숫자는 십의 자리이므로  * 10을 해줘야 한다.

 

아래의 경우에 숫자들 뒤에 0~9가 붙어있는 것이다. 따라서 10을 곱해줘야한다.

10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

이렇게 곱하는 숫자를 10씩 곱해주고, 시작숫자와 마지막 숫자를 10으로 나눠가면서 구하면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p1019 {
    static int N;
    static int start,end;
    static int multi=1;
    static int arr[] = new int[10];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        start = 1;
        end = N;
        
        
        while(start<=end) {
            
            while(start%10!=0 && start<=end) {
                solve(start);
                start++;
            }
            
            if(start>end)
                break;
            
            while(end%10!=9 && start<=end) {
                solve(end);
                end--;
            }
            start/=10;
            end/=10;
            
            
            for(int i=0; i<10; i++) {
                arr[i] += (end-start+1)*multi;
            }
            multi*=10;
            
        }
        
        for(int i=0; i<10; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    private static void solve(int s) {
        // TODO Auto-generated method stub
        while(s>0) {
            arr[s%10]+=multi;
            s/=10;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1405 미친 로봇 - Java 자바  (0) 2020.01.30
#백준_1057 토너먼트 - Java  (0) 2020.01.29
#백준_2143 두 배열의 합 - Java  (0) 2020.01.28
#백준_6603 로또 - Java  (0) 2020.01.27
#백준_1987 알파벳 - Java  (0) 2020.01.27

# 유형 : 투포인터

# upper bound, lower bound 한가지 방법과 추가로 새롭게 hashMap 을 써서 풀어보았다.

배열 사이즈가 최대 1000이라서 n^2으로 합을 다 구하고 투포인터를 사용하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package bj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
    static int N,M;
    static long T;
    static long arr_1[],arr_2[];
    static long cnt=0;
    static ArrayList<Long> arrList_1 = new ArrayList<>();
    static ArrayList<Long> arrList_2 = new ArrayList<>();
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Long.parseLong(br.readLine());
        N = Integer.parseInt(br.readLine());
        arr_1 = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
            arr_1[i] = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine());
        arr_2 = new long[M];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) 
            arr_2[i] = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<N; i++) {
            long sum = 0;
            for(int j=i; j<N; j++) {
                sum += arr_1[j];
                arrList_1.add(sum);
            }
        }
        for(int i=0; i<M; i++) {
            long sum = 0;
            for(int j=i; j<M; j++) {
                sum += arr_2[j];
                arrList_2.add(sum);
            }
        }
        Collections.sort(arrList_1);
        Collections.sort(arrList_2);
        
        int left = 0;
        int right = arrList_2.size()-1;
        
        for(int i=0; i<arrList_1.size(); i++) {
            long val = T-arrList_1.get(i);
            cnt += upper_bound(0, arrList_2.size(), val) - lower_bound(0, arrList_2.size(), val);
        }
        
        System.out.println(cnt);
    }
    public static int lower_bound(int left, int right, long target) {
        while(left<right) {
            int middle=(left+right)/2;
            if(arrList_2.get(middle) < target) {
                left = middle + 1;
            }else {
                right = middle;
            }
        }
        return right;
    }
    public static int upper_bound(int left, int right, long target) {
        while(left<right) {
            int middle=(left+right)/2;
            if(arrList_2.get(middle) <= target) {
                left = middle + 1;
            }else {
                right = middle;
            }
        }
        return right;
    }
}
 
 
 cs
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package bj;
 
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class Main {
    static int N,M;
    static long T;
    static long arr_1[],arr_2[];
    static long cnt=0;
    static ArrayList<Long> arrList_1 = new ArrayList<>();
    static ArrayList<Long> arrList_2 = new ArrayList<>();
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Long.parseLong(br.readLine());
        N = Integer.parseInt(br.readLine());
        arr_1 = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++)
            arr_1[i] = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine());
        arr_2 = new long[M];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) 
            arr_2[i] = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<N; i++) {
            long sum = 0;
            for(int j=i; j<N; j++) {
                sum += arr_1[j];
                arrList_1.add(sum);
            }
        }
        for(int i=0; i<M; i++) {
            long sum = 0;
            for(int j=i; j<M; j++) {
                sum += arr_2[j];
                arrList_2.add(sum);
            }
        }
        Collections.sort(arrList_1);
        Collections.sort(arrList_2);
        
        HashMap<Long, Integer> map = new HashMap<>();
        for(long i : arrList_1) {
            if(map.containsKey(i)) {
                map.put(i, map.get(i)+1);
            }else {
                map.put(i,1);
            }
        }
        for(long i : arrList_2) {
            if(map.containsKey(T-i)) {
                cnt += map.get(T-i);
            }
        }
        System.out.println(cnt);
    }
}
 cs

'백준' 카테고리의 다른 글

#백준_1057 토너먼트 - Java  (0) 2020.01.29
#백준_1019 책 페이지 - Java  (0) 2020.01.29
#백준_6603 로또 - Java  (0) 2020.01.27
#백준_1987 알파벳 - Java  (0) 2020.01.27
#백준_14002 가장 긴증가하는 부분 수열 4 - Java  (0) 2020.01.26

# 유형 : 탐색, DFS

# dfs 쉬운 문제중 하나, 인덱스만 잘 설정해서 탐색돌리면 해결가능

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package bj;
 
 
public class p6603_ {
    static int arr[];
    static int cnt=0;
    static int N;
    static boolean visit[];
    static ArrayList<Integer> arrList = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        while(N!=0) {
            arr = new int[N];
            visit = new boolean[N];
            for(int i=0; i<N; i++)
                arr[i] = Integer.parseInt(st.nextToken());
            
            for(int i=0; i<N; i++) {
                arrList.add(arr[i]);
                dfs(i);
                arrList.remove(0);
            }
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            System.out.println();
        }
        
    }
    public static void dfs(int index) {
        if(arrList.size() == 6) {
            for(int i=0; i<arrList.size(); i++)
                System.out.print(arrList.get(i)+" ");
            System.out.println();
            return;
        }
        
        
        for(int i=index+1; i<N; i++) {
            arrList.add(arr[i]);
            dfs(i);
            arrList.remove(arrList.size()-1);
        }
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

'백준' 카테고리의 다른 글

#백준_1019 책 페이지 - Java  (0) 2020.01.29
#백준_2143 두 배열의 합 - Java  (0) 2020.01.28
#백준_1987 알파벳 - Java  (0) 2020.01.27
#백준_14002 가장 긴증가하는 부분 수열 4 - Java  (0) 2020.01.26
#백준_12738 가장 긴 증가하는 부분 수열 3 - Java  (0) 2020.01.26

#유형 : DFS

#전형적인 dfs , 백트래킹 문제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1987 {
    static int max = 0;
    static int R,C;
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static char arr[][];
    static boolean use[] = new boolean[26];
    static boolean visit[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[R][C];
        visit = new boolean[R][C];
        for(int i=0; i<R; i++) {
            String str = br.readLine();
            for(int j=0; j<C; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        visit[0][0]=true;
        int next = arr[0][0]-65;
        use[next]=true;
        dfs(0,0,1);
        
        System.out.println(max);
    }
    
    public static void dfs(int i,int j, int cnt) {
        max = Math.max(max, cnt);
        
        for(int d=0; d<4; d++) {
            int newX = j + moveX[d];
            int newY = i + moveY[d];
            
            
            if(0<=newX && newX<C && 0<=newY && newY<R && !visit[newY][newX]) {
                int next = arr[newY][newX]-65;
                if(!use[next]) {
                    visit[newY][newX] = true;
                    use[next] = true;
                    dfs(newY,newX,cnt+1);
                    use[next] = false;
                    visit[newY][newX] = false;
                }
            }
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2143 두 배열의 합 - Java  (0) 2020.01.28
#백준_6603 로또 - Java  (0) 2020.01.27
#백준_14002 가장 긴증가하는 부분 수열 4 - Java  (0) 2020.01.26
#백준_12738 가장 긴 증가하는 부분 수열 3 - Java  (0) 2020.01.26
#백준_12015 가장 긴 증가하는 부분 수열 2 - Java  (0) 2020.01.25

+ Recent posts

티스토리툴바