#유형 : BFS, 그래프탐색

#난이도 : 골드 V

#예전에 풀었던 문제인데, 재채점하고나서 틀렸다고 떠서 다시 풀어보았다. BFS특성과 활용해 3차원 boolean 배열을 써서 문제를 해결하면 된다.

 

 
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
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 p1600 {
    static int K,W,H, arr[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static int X_move[] = {1,2,2,1,-1,-2,-2,-1};
    static int Y_move[] = {-2,-1,1,2,2,1,-1,-2};
    static boolean visit[][][];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        
        arr = new int[H+1][W+1];
        visit = new boolean[H+1][W+1][K+1];
        for(int i=1; i<=H; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=W; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(bfs());
    }
    private static int bfs() {
        // TODO Auto-generated method stub
        Queue<Po> queue = new LinkedList<>();
        queue.add(new Po(1,1,0,0));
        visit[1][1][0] = true;
        
        while(!queue.isEmpty()) {
            Po p = queue.poll();
//            System.out.println(p.y + " " + p.x + " "+ p.k + " "+p.cnt);
            // 최단값 리턴 
            if(p.y == H && p.x == W)
                return p.cnt;
            // 원숭이가 말처럼 움직일 수 있는 횟수가 남아있는 경우
            if(p.k < K) {
                for(int d=0; d<8; d++) {
                    int newX = p.x + X_move[d];
                    int newY = p.y + Y_move[d];
                    
                    if(1<=newY && newY<=H && 1<=newX && newX<=W) {
                        if(!visit[newY][newX][p.k+1] && arr[newY][newX] == 0) {
                            visit[newY][newX][p.k+1] = true;
//                            System.out.println("K"+newY+ " " +newX);
                            queue.add(new Po(newX, newY, p.k+1, p.cnt+1));
                        }
                    }
                }
            }
            // 원숭이가 말처럼 움직일 수 없는 경우 
            for(int d=0; d<4; d++) {
                int newX = p.x + moveX[d];
                int newY = p.y + moveY[d];
                if(1<=newY && newY<=H && 1<=newX && newX<=W) {
                    if(!visit[newY][newX][p.k] && arr[newY][newX] == 0) {
                        visit[newY][newX][p.k] = true;
                        queue.add(new Po(newX, newY, p.k, p.cnt+1));
                    }
                }
            }
        }
        
        return -1;
    }
    
    public static class Po{
        int x;
        int y;
        int k;
        int cnt;
        public Po(int x, int y, int k, int cnt) {
            this.x=x;
            this.y=y;
            this.k=k;
            this.cnt=cnt;
        }
    }
}
 
 cs

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

#백준_1865 웜홀 - Java 자바  (0) 2020.04.28
#백준_16593 A → B - Java 자바  (0) 2020.04.27
#백준_13549 숨바꼭질 3 - Java 자바  (0) 2020.04.25
#백준_12851 숨바꼭질 2 - Java 자바  (0) 2020.04.24
#백준_2263 트리의 순회 - Java 자바  (0) 2020.04.23

#유형 : 그래프 탐색

#난이도 : 골드 V

# https://ukyonge.tistory.com/170 문제에서 순간이동이 시간이 안늘어난다는 조건이 바뀐 문제이다. 따라서 그 부분만 수정하면 바로 해결 가능하다.

 
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
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 p13549 {
    static int N,K,cnt,min=Integer.MAX_VALUE;
    static int arr[] = new int[200001];
    static boolean visit[] = new boolean[200001];
    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());
        K = Integer.parseInt(st.nextToken());
        
        bfs();
        System.out.println(min);
    }
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<Point>();
        queue.add(new Point(N,0));
        
        while(!queue.isEmpty()) {
            Point po = queue.poll();
            visit[po.x] = true;
            
            if(po.x == K) {
                min = Math.min(min, po.y);
            }
            
            //  0초 후에 2*X
            if(po.x * 2 <= 100000 && !visit[po.x*2]) {
                queue.add(new Point(po.x*2, po.y));
            }
            //  1초 후에 X+1 
            if(po.x + 1 <= 100000 && !visit[po.x+1]) {
                queue.add(new Point(po.x+1, po.y+1));
            }
            //  1초 후에 X-1 
            if(po.x -1 >= 0 && !visit[po.x-1]) {
                queue.add(new Point(po.x-1, po.y+1));
            }
            
        }
    }
    
}
 
 cs

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

#백준_16593 A → B - Java 자바  (0) 2020.04.27
#백준_1600 말이 되고픈 원숭이 - Java 자바  (0) 2020.04.26
#백준_12851 숨바꼭질 2 - Java 자바  (0) 2020.04.24
#백준_2263 트리의 순회 - Java 자바  (0) 2020.04.23
#백준_5639 이진 검색 트리 - Java 자바  (0) 2020.04.22

#유형 : BFS, 그래프탐색

#난이도 : 골드 V

#  1초 후에 X-1 또는 X+1로 이동 / 1초 후에 2*X의 위치로 이동을 주의해주면 된다.코드에 주석을 달아놓았다.

 

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.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 p12851 {
    static int N,K,cnt,min=0;
    static int arr[] = new int[100001];
    static boolean visit[] = new boolean[100001];
    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());
        K = Integer.parseInt(st.nextToken());
        
        bfs();
        System.out.println(min);
        System.out.println(cnt);
    }
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<Point>();
//        수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다
        visit[N] = true;
        queue.add(new Point(N,0));
        
        while(!queue.isEmpty()) {
            Point po = queue.poll();
            visit[po.x] = true;
            // 이미 목적지가 방문이 되어있는 경우
            if(min!=0 && min==po.y && po.x == K) {
                cnt++;
            }
            // 목적지 방문이 처음인 경우
            if(min ==0 && po.x == K) {
                min = po.y;
                cnt++;
            }
            //  1초 후에 X+1 
            if(po.x + 1 < 100001 && !visit[po.x+1])
                queue.add(new Point(po.x+1, po.y+1));
            //  1초 후에 X-1 
            if(po.x -1 >= 0 && !visit[po.x-1])
                queue.add(new Point(po.x-1, po.y+1));
            //  1초 후에 2*X
            if(po.x * 2 < 100001 && !visit[po.x*2])
                queue.add(new Point(po.x*2, po.y+1));
        }
    }
    
    
}
 
 cs

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

#백준_1600 말이 되고픈 원숭이 - Java 자바  (0) 2020.04.26
#백준_13549 숨바꼭질 3 - Java 자바  (0) 2020.04.25
#백준_2263 트리의 순회 - Java 자바  (0) 2020.04.23
#백준_5639 이진 검색 트리 - Java 자바  (0) 2020.04.22
#백준_9663 N-Queen - Java 자바  (0) 2020.04.21

#유형 : 트리, 자료구조

#난이도 : 골드 3

 

# 1) postOrder의 마지막 원소가 트리의 루트라는 특징을 이용하여 inOrder(좌우로 나뉜다는 특징)에서 
1. 첫번째 인덱스  ~  해당 인덱스-1  //// 2. 해당 인덱스+1  ~ 마지막 인덱스 로 분할 한다.

 

# 2) postOrder를 다음과 같이 분할

1. 후위 배열의 첫번째 인덱스 ~ 찾은인덱스 - 중위순회에서의 첫 인덱스 - 1
2. 후위 배열의 첫번째 인덱스 + 찾은인덱스 - 중위순회에서의 첫 인덱스 ~ 마지막 인덱스 -1 로 나누어준다.

 

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 p2263 {
    static int N;
    static int in[],post[],idx[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        in = new int[N+1];
        post = new int[N+1];
        idx = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            in[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            post[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=1; i<=N; i++)
            idx[in[i]] = i;
        
        
        preOrder(0, N, 0, N);
    }
    public static void preOrder(int in_begin, int in_end, int post_begin, int post_end) {
        if(in_begin > in_end || post_begin > post_end || post_end == 0)
            return;
        
        int root = post[post_end];
        System.out.print(root+" ");
        
        int left = idx[root] - in_begin;
                
        //Left
        preOrder(in_begin, idx[root] - 1, post_begin, post_begin + left -1);
        //right
        preOrder(idx[root] + 1, in_end, post_begin + left, post_end - 1);
    }
}
 
 cs

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

#백준_13549 숨바꼭질 3 - Java 자바  (0) 2020.04.25
#백준_12851 숨바꼭질 2 - Java 자바  (0) 2020.04.24
#백준_5639 이진 검색 트리 - Java 자바  (0) 2020.04.22
#백준_9663 N-Queen - Java 자바  (0) 2020.04.21
#백준_1058 친구 - Java 자바  (0) 2020.04.17

#유형 : 트리, 자료구조

# 난이도 : 실버 1

# 자료구조 강의 듣던 시절로 돌아간 느낌이었다. 입력으로 들어오는 PreOrder 를 조건에 맞게 트리로 작성한다음 postOrder로 출력하면 된다.

 

# 현재 노드의 값보다 작으면 왼쪽으로 노드 삽입, 그 반대인 경우에는 오른쪽으로 삽입한다.(중복값없음).

 

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
package bj;
 
import java.io.IOException;
import java.util.Scanner;
 
public class p5639 {
    static int arr[] = new int[10001];
    public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Node root = new Node(N);
        while(sc.hasNext()) {
            try {
                N = sc.nextInt();
                root = insertNode(root, N);
            } catch (Exception e) {
                // TODO: handle exception
                break;
            }
            
        }
        postOrder(root);
    }
    public static class Node{
        Node left;
        Node right;
        int val;
        public Node(int v) {
            this.val = v;
        }
        
    }
    public static Node insertNode(Node node, int N) {
        Node current = null;
        if(node == null) {
            return new Node(N);
        }
        
        if(node.val > N) {
            current = insertNode(node.left, N);
            node.left = current;
        }else {
            current = insertNode(node.right, N);
            node.right = current;
        }
        return node;
    }
    
    public static void postOrder(Node node) {
        if(node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.val);
        }
    }
}
 
 cs

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

#백준_12851 숨바꼭질 2 - Java 자바  (0) 2020.04.24
#백준_2263 트리의 순회 - Java 자바  (0) 2020.04.23
#백준_9663 N-Queen - Java 자바  (0) 2020.04.21
#백준_1058 친구 - Java 자바  (0) 2020.04.17
#백준_2665 미로만들기 - Java 자바  (0) 2020.04.14

# 유형 : 백트래킹

# 난이도 : 골드 V

 

 

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p9663 {
    static int N,count;
    static int cols[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cols = new int[16];
        batch(0);
        System.out.println(count);
    }
    
    public static boolean isPossible(int idx) {
        int tmp = 1;
        boolean rs = true;
        while(tmp<idx && rs) {
            // 같은 행이거나 또는 대각선의 관계를 가질 때 배치할 수 없다.
            if(cols[idx] == cols[tmp] || Math.abs(cols[idx]-cols[tmp]) == idx-tmp)
                rs = false;
            tmp++;
        }
        return rs;
    }
    
    public static void batch(int idx) {
        if(isPossible(idx)) {
            if(idx==N) {
                count++;
            }
            else {
                //행의 값을 넣어가며 배치가 가능한지 확인한다.
                for(int j=1; j<=N; j++) {
                    cols[idx + 1] = j;
                    batch(idx+1);
                }
            }
        }
    }
    
}
 
 cs

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

#백준_2263 트리의 순회 - Java 자바  (0) 2020.04.23
#백준_5639 이진 검색 트리 - Java 자바  (0) 2020.04.22
#백준_1058 친구 - Java 자바  (0) 2020.04.17
#백준_2665 미로만들기 - Java 자바  (0) 2020.04.14
#백준_1753 최단경로 - Java 자바  (0) 2020.04.06

#유형 : 그래프 탐색

# 난이도 : 실버 1

# 거쳐가는 정점을 기준으로 문제를 푸는 플로이드 와샬의 전형적인 문제였다. 입력이 N으로 주어지는 부분을 Integer.MAX_VALUE로 처리했더니 11%에서 계속 틀렸다고 떠서 잘못풀었나했는데.. 987654321 값을 주니 또 통과하였다.. 왜 그런지 알 수가없다., 

 

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
package bj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p1058 {
    static int N, result = 0;
    static int arr[][];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            String str = br.readLine();
            for(int j=1; j<=N; j++) {
                char ch = str.charAt(j-1);
                
                if(ch == 'Y')
                    arr[i][j] = 1;
                
                else if(i != j)
                    arr[i][j] = 987654321;
                
            }
        }
        floyd_warshall();
        for(int i=1; i<=N; i++) {
            int tmp = 0;
            for(int j=1; j<=N; j++) {
                if(i==j)
                    continue;
                // 한 다리 건너서 아는 친구 + 서로 친구
                else if(arr[i][j] <= 2)
                    tmp++;
            }
            result = Math.max(result, tmp);
        }
        System.out.println(result);
    }
    public static void floyd_warshall() {
        for(int k=1; k<=N; k++) {
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(i==j || j==k || i==k)
                        continue;
                    else if(arr[i][j] > arr[i][k] + arr[k][j])
                        arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }
}
 
 cs

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

#백준_5639 이진 검색 트리 - Java 자바  (0) 2020.04.22
#백준_9663 N-Queen - Java 자바  (0) 2020.04.21
#백준_2665 미로만들기 - Java 자바  (0) 2020.04.14
#백준_1753 최단경로 - Java 자바  (0) 2020.04.06
#백준_10835 카드게임 - Java 자바  (0) 2020.04.04

# 유형 : 그래프 탐색

# 난이도 : 골드 4

# 벽을 최소한으로 부수고 목적지까지 가는 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
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;
 
public class p2665 {
    static int N;
    static int arr[][], map[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static int maxValue = Integer.MAX_VALUE;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        map = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            String str = br.readLine();
            for(int j=1; j<=N; j++) {
                arr[i][j] = str.charAt(j-1)-'0';
                map[i][j] = Integer.MAX_VALUE;
            }
        }
        bfs(1,1);
//        for(int i=1; i<=N; i++) {
//            for(int j=1; j<=N; j++) {
//                System.out.print(map[i][j]+" ");
//            }System.out.println();
//        }
        System.out.println(map[N][N]);
    }
    
    public static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x,y));
        map[y][x] = 0;
        while(!queue.isEmpty()){
            Point p = queue.poll();
            
            for(int d=0; d<4; d++) {
                int newX = p.x + moveX[d];
                int newY = p.y + moveY[d];
                
                //범위안에 속하면서 다음 좌표가 갱신이 아직 안되어있거나 더 크다면 => 더 작은값으로 갱신할수 있다면 
                if(1<=newX && newX<=N && 1<=newY && newY<=N && map[newY][newX] > map[p.y][p.x]) {
                    if(arr[newY][newX] == 1) {
                        queue.add(new Point(newX, newY));
                        map[newY][newX] = map[p.y][p.x];
                    }else {
                        queue.add(new Point(newX, newY));
                        map[newY][newX] = map[p.y][p.x] + 1;
                    }
                }
            }
        }
    }
    
    
}
 
 cs

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

#백준_9663 N-Queen - Java 자바  (0) 2020.04.21
#백준_1058 친구 - Java 자바  (0) 2020.04.17
#백준_1753 최단경로 - Java 자바  (0) 2020.04.06
#백준_10835 카드게임 - Java 자바  (0) 2020.04.04
#백준_17142 연구소 3 - Java 자바  (0) 2020.04.03

+ Recent posts

티스토리툴바