# 유형 :유클리드호제, 수학

# 난이도 : 실버 1

# 맨 처음에는 배열을 입력받아서 그 배열 전체의 최대공약수를 한번에 구하는 함수를 구현했는데 9%정도에서 시간초과가 계속 떠서 포기하고, 정렬한 배열의 인접한 수 사이의 최대공약수를 구하는 방식으로 접근했다. 최대공약수 구하는 방법은 유클리드 호제 알고리즘을 사용하였고, 약수 구하는 부분은 그냥 i부터 최대공약수까지 반복문을 돌렸다. 하지만 약수 구하는 부분도 효율적이게 짜려면 반복문 조건을 i*i <= 최대공약수로 하고, i값과 최대공약수/i로 하여 리스트에 넣고 정렬을 하면 된다.(중복값도 제거)

 

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
package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class p2981 {
    static int N;
    static int arr[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        
        int val = arr[1]-arr[0];
        for(int i=2; i<N; i++) {
            val = getGCD(val, arr[i] - arr[i-1]);
        }
        StringBuffer sb = new StringBuffer();
        for(int i=2; i<=val; i++) {
            if(val%i == 0) {
                sb.append(i+" ");
            }
        }
        System.out.println(sb.toString());
        
    }
    public static int getGCD(int a, int b) {
        if(a%b == 0) {
            return b;
        }
        
        return getGCD(b, a%b);
    }
}
 
 cs

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

#백준_1939 중량제한 - Java 자바  (0) 2020.03.07
#백준_5567 결혼식 - Java 자바  (0) 2020.03.06
#백준_1726 로봇 - Java 자바  (0) 2020.03.05
#백준_1039 교환 - Java 자바  (0) 2020.03.04
#백준_1614 영식이의 손가락 - Java 자바  (0) 2020.03.04

#유형 : 그래프 탐색, 구현, BFS

#난이도 : 골드 4

# BFS+시뮬레이션 문제였다. 기본적인 BFS에 명령 1.Go k, 명령2. Turn dir를 구현해주면 된다. 또 생각없이 풀다가

방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4 라는것을 보고 코드를 또 수정했다. Go 명령은 k(1,2,3)번 가는데 예를 들어 1번 가는데도 막히면 2,3번 가는것도 막히니 break 처리해주는 것이 좋다.

 

*정리 : 현재 방향으로 1, 2, 3칸을 갈 수 있는지 반복문을 통해 확인하는 부분 + 현재 위치에서 방향 전환할 수 있는지,, 최대가 180도임 270도, 360도는 돌 필요도 없고 최대가 count+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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1726 {
    //방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4
    static int moveX[] = {0,1,-1,0,0};
    static int moveY[] = {0,0,0,1,-1};
    static int M,N;
    static int arr[][];
    static boolean visit[][][];
    static Po start, end;
    static int result = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        //직사각형의 세로 길이 M과 가로 길이 N
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        arr = new int[101][101];
        visit = new boolean[101][101][5];
        for(int m=0; m<M; m++) {
            st = new StringTokenizer(br.readLine());
            for(int n=0; n<N; n++) {
                arr[m][n] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());
        int y = Integer.parseInt(st.nextToken())-1;
        int x = Integer.parseInt(st.nextToken())-1;
        int dir = Integer.parseInt(st.nextToken());
        
        start = new Po(x,y,dir,0);
        
        st = new StringTokenizer(br.readLine());
        y = Integer.parseInt(st.nextToken())-1;
        x = Integer.parseInt(st.nextToken())-1;
        dir = Integer.parseInt(st.nextToken());
        
        end = new Po(x,y,dir,0);
        
        bfs();
        System.out.println(result);
    }
    
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Po> queue = new LinkedList<>();
        visit[start.y][start.x][start.dir] = true;
        queue.add(start);
        while(!queue.isEmpty()) {
            Po p = queue.poll();
//            System.out.println(p.y+" "+p.x+" "+p.dir+" "+p.cnt);
            if(p.y == end.y && p.x == end.x && p.dir == end.dir) {
                result = p.cnt;
                return;
            }
            
            //명령 1. Go k - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
            for(int k=1; k<=3; k++) {
                int newY = p.y + moveY[p.dir]*k;
                int newX = p.x + moveX[p.dir]*k;
                
                if(0<=newY && newY<M && 0<=newX && newX<N && arr[newY][newX]==0) {
                    if(visit[newY][newX][p.dir])
                        continue;
                    visit[newY][newX][p.dir] = true;
                    queue.add(new Po(newX, newY, p.dir, p.cnt+1));
                }else {
                    break;
                }
            }
            //명령 2. Turn dir - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.
            for(int d=1; d<=4; d++) {
                if(p.dir != d && !visit[p.y][p.x][d]) {
                    visit[p.y][p.x][d] = true;
                    //방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4
                    if((p.dir==1 && d==2) || (p.dir==2 && d==1) || (p.dir==3 && d==4) || (p.dir==4 && d==3)) {
                        queue.add(new Po(p.x, p.y, d, p.cnt+2));
                    }else
                        queue.add(new Po(p.x, p.y, d, p.cnt+1));
                }
            }
            
        }
    }
 
    public static class Po{
        int x;
        int y;
        int dir;
        int cnt;
        public Po(int x,int y,int dir, int cnt) {
            this.x=x;
            this.y=y;
            this.dir=dir;
            this.cnt=cnt;
        }
    }
}
 
 cs

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

#백준_5567 결혼식 - Java 자바  (0) 2020.03.06
#백준_2981 검문 - Java 자바  (0) 2020.03.06
#백준_1039 교환 - Java 자바  (0) 2020.03.04
#백준_1614 영식이의 손가락 - Java 자바  (0) 2020.03.04
#백준_3006 터보소트 - Java 자바  (0) 2020.03.03

#유형 : 그래프 탐색, BFS

#난이도 : 골드 3

# 맨 처음에는 어떻게 교환을 해야 가장 큰 수를 얻을 수 있을까 라는 생각으로 문제를 접근했다가 망했다. 이 문제에서 요구하는 것은 그것이 아니라 **K번의 위치 교환을 수행한 수 중에 가장 큰 수** 를 구하는 것이었다. 따라서 swap하여 중첩되지 않는 수를 큐에 넣으면서 구하는 문제였다. 이 때 중첩되지 않는 수는 어떻게 처리해야할까 생각하다가 1차원으로 처리하면 똑같은 수로 이루어진 4444, 5555 같은 숫자는 첫 번째 교환 후 연산을 할 수 없다. 따라서 2차원 boolean형 배열로 해결하였고, 또한 맨 앞자리가 0이 와선 안되므로 swap 할때 조건을 따져줘야 한다. 2차원 배열로 해도 되고, 아니면 1차원 배열을 사용하려면 큐 사이즈 만큼 반복문을 돌리면서 연산 한번을 수행할 때마다 배열을 초기화시켜주면 될 것같다.

 

필자의 경우에는 위치를 바꿔주기 위해 StringBulider 클래스를 사용하였는데 애초에 큐에 넣는 값을 String으로 넣어 toCharArray()를 통해 교환을 하는 것도 좋아보인다. 사람마다 방식은 다르니 참고만 하시길.

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
package bj;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1039 {
 
    static boolean visit[][] = new boolean[1000001][11];
    static int N,K;
    static String str;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        str = st.nextToken();
        N = Integer.parseInt(str);
        K = Integer.parseInt(st.nextToken());
        
        bfs();
        
    }
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(N, 0));
        visit[N][0] = true;
        while(!queue.isEmpty()) {
            
            if(queue.peek().y == K)
                break;
            
            Point po = queue.poll();
            for(int i=0; i<str.length()-1; i++) {
                for(int j=i+1; j<str.length(); j++) {
                    int next = solve(po.x, i, j);
                    if(next != -1 && !visit[next][po.y+1]) {
                        visit[next][po.y+1] = true;
                        queue.add(new Point(next, po.y+1));
                    }
                }
            }
        }
        int result = -1;
        while(!queue.isEmpty()) {
            Point po = queue.poll();
//            System.out.println(po.x);
            if(result < po.x)
                result = po.x;
        }
        
        System.out.println(result);
        
        
    }
    private static int solve(int x, int i, int j) {
        // TODO Auto-generated method stub
        StringBuilder sb = new StringBuilder();
        sb.append(x);
        if(i==0 && sb.charAt(j)=='0')
            return -1;
        
        char tmp = sb.charAt(i);
        sb.setCharAt(i, sb.charAt(j));
        sb.setCharAt(j, tmp);
        return Integer.parseInt(sb.toString());
    }
}
 cs

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

#백준_2981 검문 - Java 자바  (0) 2020.03.06
#백준_1726 로봇 - Java 자바  (0) 2020.03.05
#백준_1614 영식이의 손가락 - Java 자바  (0) 2020.03.04
#백준_3006 터보소트 - Java 자바  (0) 2020.03.03
#백준_3187 양치기 꿍 - Java 자바  (0) 2020.03.03

# 유형 : 시뮬레이션, 점화식

# 난이도 : 실버 1

# 탐색으로도 분류되어 있어서 가볍게 탐색으로 짜봤는데 시간초과가 나서 그냥 점화식을 세워서 해결했다. 아래와 같이 점화식을 세워 해결해가면 된다. 주의해야할 점은 값이 Integer형을 넘는 범위를 갖는 답도 있기 때문에 long 타입형으로 출력해야 틀리지 않는다.

1) 만약 첫 번째 손가락인 경우 => 사용 횟수 * 8

0 0
1 8
2 16
3 24
4 32
5 40
6 48

2) 두 번째 손가락인 경우 => 두 번째 손가락은 기본적으로 첫 번째 손가락을 포함하기 때문에 식에 기본적으로 1씩 더해준다. 짝수 일때마다 8을 더해주는 것을 확인할 수 있고, 홀수의 경우에는 8씩 추가가 된다. => 1 + (사용횟수/2) * 8 + (사용횟수%2) * 6

0 1
1 7
2 9
3 15
4 17
5 23
6 25

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p1614 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long hurt = Long.parseLong(br.readLine());
        long num = Long.parseLong(br.readLine());
        long result;
        if(hurt == 1) {
            result = (long)(num*8);
        }else if(hurt == 2) {
            result = (long)(1+(num/2)*8+(num%2)*6);
        }else if(hurt == 3) {
            result = (long)(2+(num/2)*8+(num%2)*4);
        }else if(hurt == 4) {
            result = (long)(3+(num/2)*8+(num%2)*2);
        }else {
            result = (long)(4 + num*8);
        }
        System.out.println(result);
    }
}
 
 cs

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

#백준_1726 로봇 - Java 자바  (0) 2020.03.05
#백준_1039 교환 - Java 자바  (0) 2020.03.04
#백준_3006 터보소트 - Java 자바  (0) 2020.03.03
#백준_3187 양치기 꿍 - Java 자바  (0) 2020.03.03
#백준_2234 성곽 - Java 자바  (0) 2020.03.02

#유형 : 시뮬레이션, 펜윅 트리

#난이도 : 플래티넘 4

# 맨 처음에는 트리문제로 접근안하고 그냥 구현해서 풀었는데, 풀고나서 보니 다른 사람들은 펜윅 트리 알고리즘으로 풀어서 도전해보았다. 

펜윅 트리는 https://www.crocus.co.kr/666에  정말 설명이 잘 되어있다. 필자가 설명하기 보다는 저 블로그에 정리가 잘되어있으니 참고하면 좋을 것 같다. 코드는 1) 시뮬레이션 2)펜윅 트리로 첨부한다.

 

# 펜윅 트리로 접근한 방식

5

5 4 3 2 1 로 생각해보자. 모든 인덱스에는 1이라는 값을 넣는다. 그렇다면 

1 1 1 1 1 이라는 값이 들어있을 것이다.

1) 처음에는 숫자 1을 찾아야 한다. 1은 5 번째에 있기에 앞으로 4칸을 땡겨야 한다.

그렇다면 1 1 1 1 1 에서 처음부터 5번째 인덱스까지 더한 후에 -1을 한다면 4를 얻을 수 있다.

그 후에 1 1 1 1 0 으로 배열을 변경해준다.

 

2) 그다음은 5를 옮겨야하는데 1번째에 있다.

이 값은 1 1 1 1 0 에서 첫 번째 인덱스에서 오른쪽으로 모든 합을 더한 후 -1을 하게 되면 3이라는 값을 얻을 수 있다.

그 후 0 1 1 1 0 으로 배열을 변경해준다.

 

이러한 방법을 반복하여 접근한다면 자바 Point 객체(값, 인덱스)와 펜윅트리의 update, sum 함수를 이용하여 풀 수 있다

 

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
package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class p3006 {
    static int N, low, high;
    static int arr[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        for(int n=0; n<N; n++) {
            arr[n] = Integer.parseInt(br.readLine());
        }
        StringBuilder sb = new StringBuilder();
        low = 0;
        high = N-1;
        int max = N;
        int min = 1;
        int time = 1;
        while(low < high) {
            int rs = 0;
            int index =0 ;
            
            if(time % 2 == 1) {
                for(int i=low; i<=high; i++) {
                    if(min == arr[i]) {
                        index = i;
                        break;
                    }
                }
                for(int i=index; i>low; i--) {
                    int tmp = arr[i];
                    arr[i] = arr[i-1];
                    arr[i-1] = tmp;
                }
                rs += (index - low);
                low++;
                min++;
            }
            else {
                for(int i=low; i<=high; i++) {
                    if(max == arr[i]) {
                        index = i;
                        break;
                    }
                }
                for(int i=index; i<high; i++) {
                    int tmp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tmp;
                }
                rs += (high - index);
                high--;
                max--;
            }
            sb.append(rs+"\n");
            time++;
        }
        sb.append("0\n");
        System.out.println(sb.toString());
        
    }
}
 
 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
66
67
68
69
70
71
72
package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
 
public class p3006_tree {
    static int N, low, high;
    static int tree[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new int[N+1];
        ArrayList<Po> arrList = new ArrayList<>();
        arrList.add(new Po(0,0));
        for(int n=1; n<=N; n++) {
            int x = Integer.parseInt(br.readLine());
            arrList.add(n, new Po(x, n));
            update(n, 1);
        }
        Collections.sort(arrList);
        int low = 1;
        int high = N;
        for(int i=1; i<=N; i++) {
            if(i%2 == 1) {
                System.out.println(sum(arrList.get(low).y)-1);
                update(arrList.get(low).y, -1);
                low++;
            }else {
                System.out.println(sum(N)- sum(arrList.get(high).y-1)-1);
                update(arrList.get(high).y, -1);
                high--;
            }
        }
    }
    
    public static int sum(int index) {
        int rs = 0;
        while(index > 0) {
            rs += tree[index];
            index -= (index & -index);
        }
        return rs;
    }
    public static void update(int index, int diff) {
        while(index<=N) {
            tree[index] += diff;
            index += (index & -index);
        }
    }
    
    public static class Po implements Comparable<Po>{
        int x;
        int y;
        
        public Po(int x, int y) {
            this.x=x;
            this.y=y;
        }
        @Override
        public int compareTo(Po o) {
            if(this.x - o.x > 0)
                return 1;
            
            return -1;
        }
        
    }
}
 
 cs

 

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

#백준_1039 교환 - Java 자바  (0) 2020.03.04
#백준_1614 영식이의 손가락 - Java 자바  (0) 2020.03.04
#백준_3187 양치기 꿍 - Java 자바  (0) 2020.03.03
#백준_2234 성곽 - Java 자바  (0) 2020.03.02
#백준_3987 보이저 1호 - Java 자바  (0) 2020.03.02

# 유형 : 그래프 탐색, BFS

# 난이도 : 실버 2

# 울타리로 구분되어있는 부분을 BFS탐색을 돌리며 양과 늑대의 수를 체크한 다음 계산해주면 되었던 전형적인 BFS문제

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
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p3187 {
    static int R,C;
    static char arr[][];
    static boolean visit[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    public static void main(String[] args) throws Exception{
        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];
        int sheep = 0;
        int wolf = 0;
        for(int r=0; r<R; r++) {
            String str = br.readLine();
            for(int c=0; c<C; c++) {
                arr[r][c] = str.charAt(c);
            }
        }
        for(int r=0; r<R; r++) {
            for(int c=0; c<C; c++) {
                if(arr[r][c] != '#' && !visit[r][c]) {
                    Point po = bfs(r,c);
                    wolf += po.x;
                    sheep += po.y;
                }
            }
        }
        System.out.println(sheep +" " +wolf);
    }
    private static Point bfs(int row, int col) {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<Point>();
        visit[row][col] = true;
        queue.add(new Point(col, row));
        int sheep = 0;
        int wolf = 0;
        while(!queue.isEmpty()) {
            Point po = queue.poll();
            if(arr[po.y][po.x] == 'v')
                wolf++;
            else if(arr[po.y][po.x] == 'k')
                sheep++;
            
            for(int d=0; d<4; d++) {
                int newY = po.y + moveY[d];
                int newX = po.x + moveX[d];
                
                if(0<=newY && newY<R && 0<=newX && newX<C && !visit[newY][newX] && arr[newY][newX] != '#') {
                    visit[newY][newX] = true;
                    queue.add(new Point(newX, newY));
                }
            }
        }
        if(wolf>=sheep) {
            sheep = 0;
        }else {
            wolf = 0;
        }
        
        return new Point(wolf, sheep);
    }
}
 
 cs

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

#백준_1614 영식이의 손가락 - Java 자바  (0) 2020.03.04
#백준_3006 터보소트 - Java 자바  (0) 2020.03.03
#백준_2234 성곽 - Java 자바  (0) 2020.03.02
#백준_3987 보이저 1호 - Java 자바  (0) 2020.03.02
#백준_15684 사다리 조작 - Java 자바  (0) 2020.02.29

# 유형 : BFS + 비트 마스크

# 난이도 : 골드 4

# BFS + 비트 마스크 알고리즘을 사용하여 접근한 문제. 맨 처음에는 비트 마스크 안 쓰고 하려 했는데, 코드가 너무 길어지는 것 같아서 비트 마스크를 사용하였다. 

*** 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8 *** 

예를 들어 15가 주어지면 1,2,4,8로 비트 체킹을 하면 다 1,2,4,8을 출력한다. 이 경우에는 4가지 방향 모두 벽이 있다는 뜻이다. 13의 경우에는 1,0,4,8을 출력하므로 북쪽에는 벽이 없다는 말이다. 따라서 비트 마스크를 사용하여 다음 방향으로 이동할 수 있는지를 체크하며 BFS를 진행하면 된다. BFS를 호출한 횟수가 방의 개수이고, 벽을 제거했을 때도 똑같이 비트마스크를 사용하며 벽을 허물고 BFS 돌리면서 해결하면 된다.

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
90
91
92
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2234 {
    static int R,C;
    static int arr[][];
    static boolean visit[][];
    static int moveX[] = {-1,0,1,0};
    static int moveY[] = {0,-1,0,1};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        
        arr = new int[R][C];
        visit = new boolean[R][C];
        for(int r=0; r<R; r++) {
            st = new StringTokenizer(br.readLine());
            for(int c=0; c<C; c++) {
                arr[r][c] = Integer.parseInt(st.nextToken());
            }
        }
        
        int room = 0;
        int max = 0;
        for(int r=0; r<R; r++) {
            for(int c=0; c<C; c++) {
                if(!visit[r][c]) {
                    max = Math.max(max, bfs(r,c));
                    room++;
                }
            }
        }
        System.out.println(room);
        System.out.println(max);
 
        for(int r=0; r<R; r++) {
            for(int c=0; c<C; c++) {
                for(int bit=1; bit<=8; bit<<=1) {
                    if((arr[r][c] & bit)!=0) {
                        visit = new boolean[R][C];
                        arr[r][c] -= bit;
                        max = Math.max(max, bfs(r,c)); 
                        arr[r][c] += bit;
                    }
                }
            }
        }
//        이 성에 있는 방의 개수
//        가장 넓은 방의 넓이
//        하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
        System.out.println(max);
    }
    private static int bfs(int row, int col) {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(col, row));
        visit[row][col] = true;
        int count = 1;
        while(!queue.isEmpty()) {
            
            Point po = queue.poll();
            int bit = 1;
//            System.out.println(po);
            for(int d=0; d<4; d++) {
                if((arr[po.y][po.x] & bit)==0) {
                    int newX = po.x + moveX[d];
                    int newY = po.y + moveY[d];
                    if (!(0 <= newY && newY < R && 0 <= newX && newX < C))
                         continue;
                    if(0<=newY && newY<R && 0<=newX && newX<C && !visit[newY][newX]) {
                        count++;
                        visit[newY][newX]=true;
                        queue.add(new Point(newX, newY));
                    }
                }
                bit<<=1;
            }
        }
        return count;
    }
    
    
}
 
 cs

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

#백준_3006 터보소트 - Java 자바  (0) 2020.03.03
#백준_3187 양치기 꿍 - Java 자바  (0) 2020.03.03
#백준_3987 보이저 1호 - Java 자바  (0) 2020.03.02
#백준_15684 사다리 조작 - Java 자바  (0) 2020.02.29
#백준_1347 미로 만들기 - Java 자바  (0) 2020.02.29

# 유형 : 구현, 탐색

# 난이도 : 실버 3

# 난이도치고는 꽤 짜증났던 문제.. 구현+탐색은 항상 귀찮다. 현재 방향과 행성의 종류에 따라 전파 방향을 잘 따져주어야 하고 무엇보다 방문체크 생각없이 2차원으로 했는데, 들어오는 방향에 따라 같은 곳을 두번 방문할수도 있다.( Voyager이 아님에도 불구하고)

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p3987 {
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static int N,M;
    static char arr[][];
    static boolean visit[][][];
    static boolean isPossible = false;
    static Point start;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new char[N][M];
        for(int n=0; n<N; n++) {
            String str = br.readLine();
            for(int m=0; m<M; m++) {
                arr[n][m] = str.charAt(m);
            }
        }
        st = new StringTokenizer(br.readLine());
        int y = Integer.parseInt(st.nextToken())-1;
        int x = Integer.parseInt(st.nextToken())-1;
        start = new Point(x,y);
        int maxValue = 0;
        int direction = 0;
        for(int d=0; d<4; d++) {
            visit = new boolean[N][M][4];
            visit[start.y][start.x][d] = true;
            int rs = solve(d, start);
            if(isPossible) {
                direction = d;
                break;
            }
            if(maxValue < rs) {
                direction = d;
                maxValue = rs;
            }
        }
        char ch;
        if(direction == 0) {
            ch = 'U';
        }else if(direction == 1) {
            ch = 'R';
        }else if(direction == 2) {
            ch = 'D';
        }else{
            ch = 'L';
        }
        
        if(isPossible) {
            System.out.println(ch);
            System.out.println("Voyager");
        }else{
            System.out.println(ch);
            System.out.println(maxValue);
        }
            
        
        
    }
    private static int solve(int d, Point p) {
        int result = 1;
        
        int x = p.x;
        int y = p.y;
        
        while(true) {
            int newX = x + moveX[d];
            int newY = y + moveY[d];
            int newDir = d;
            if(0<=newX && newX<M && 0<=newY && newY<N) {
                if(arr[newY][newX] == 'C')
                    break;
                if(arr[newY][newX] == '.' && visit[newY][newX][newDir]) {
                    isPossible = true;
                    break;
                }
                
                result++;
                
                if(arr[newY][newX] == '/') {
                    newDir = getDir(d, arr[newY][newX]);
                }else if(arr[newY][newX] == '\\'){
                    newDir = getDir(d, arr[newY][newX]);
                }
                
                visit[newY][newX][newDir] = true;
                x = newX;
                y = newY;
                d = newDir;
            }else
                break;
        }
        
        return result;
    }
    private static int getDir(int d, char c) {
        if(c == '/') {
            if(d==0) {
                return 1;
            }else if(d==1) {
                return 0;
            }else if(d==2) {
                return 3;
            }else if(d==3) {
                return 2;
            }
        }else if(c == '\\') {
            if(d==0) {
                return 3;
            }else if(d==1) {
                return 2;
            }else if(d==2) {
                return 1;
            }else if(d==3) {
                return 0;
            }
        }
        // TODO Auto-generated method stub
        return 0;
    }
}
 
 cs

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

#백준_3187 양치기 꿍 - Java 자바  (0) 2020.03.03
#백준_2234 성곽 - Java 자바  (0) 2020.03.02
#백준_15684 사다리 조작 - Java 자바  (0) 2020.02.29
#백준_1347 미로 만들기 - Java 자바  (0) 2020.02.29
#백준_2933 미네랄 - Java 자바  (0) 2020.02.27

+ Recent posts

티스토리툴바