# 유형 : 시뮬레이션

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1592 {
    static int N,M,L;
    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());
        M = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
    
        int arr[] = new int[N];
        int cnt=0;
        int index=0;
        while(true) {
            arr[index]++;
            if(arr[index] == M)
                break;
            
            if(arr[index]%2 == 0) {
                if(index + L >= N) {
                    index = L-N+index;
                }else {
                    index+=L;
                }
            }else if(arr[index]%2 ==1){
                if(index-L<0) {
                    index = N-L+index;
                }else
                    index-=L;
            }
            cnt++;
        }
        System.out.println(cnt);
    }
}
 
 cs

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

#백준_2931 가스관 - Java 자바  (0) 2020.02.18
#백준_9205 맥주 마시면서 걸어가기 - Java 자바  (0) 2020.02.17
#백준_1613 역사 - Java 자바  (0) 2020.02.16
#백준_6593 상범 빌딩 - Java 자바  (0) 2020.02.15
#백준_1389 케빈 베이컨의 6단계 법칙  (0) 2020.02.15

# 유형 : 탐색, 플로이드 와샬

# dfs,bfs 로도 풀 수 있지만 문제를 보면 시작점, 도착점, 중간점을 이용해서 문제를 해결할 수 있다. 예를 들어 1번 사건이 2번 사건보다 먼저 일어났고, 2번 사건이 3번 사건 보다 먼저 일어났다면 1번과 3번중에 먼저 일어난 사건은 1번이다. 플로이드 와샬로 해결해보자면 1번이 시작점, 2번이 중간점, 3번이 도착점이다.

예를 들어 1은 뒤에가 먼저 일어난 사건일 경우, -1은 앞에가 먼저 일어난 사건일 경우, 0은 모르는 경우이다. 따라서 맨 처음에는 모르는 경우로 초기화를 해주고  if(arr[i][j] == 0) {(arr[i][k] == 1 && arr[k][j] == 1 )} ======> arr[i][j] = 1

이런식으로 -1, 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
47
48
49
50
51
52
53
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1613 {
    static int N,K,S;
    static int arr[][];
    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());
        
        arr = new int[N+1][N+1];
        for(int i=0; i<K; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            arr[u][v] = -1;
            arr[v][u] = 1;
        }
        
        floyd_warshall();
        
        S = Integer.parseInt(br.readLine());
        for(int s=0; s<S; s++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            System.out.println(arr[u][v]);
        }
        
    }
    
    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(arr[i][j] == 0) {
                        if(arr[i][k] == 1 && arr[k][j] == 1)
                            arr[i][j] = 1;
                        else if(arr[i][k] == -1 && arr[k][j] == -1)
                            arr[i][j] = -1;
                    }
                }
            }
        }
    }
}
 
 cs

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

#백준_9205 맥주 마시면서 걸어가기 - Java 자바  (0) 2020.02.17
#백준_1592 영식이와 친구들 - Java 자바  (0) 2020.02.16
#백준_6593 상범 빌딩 - Java 자바  (0) 2020.02.15
#백준_1389 케빈 베이컨의 6단계 법칙  (0) 2020.02.15
#백준_2668 숫자고르기 - Java 자바  (0) 2020.02.14

# 유형 : 그래프, BFS

# 보통 풀던 2차원에서 3차원으로 확대한 문제 및 입력시 공백라인 들어오는 것을 처리해주면 어렵지 않게 해결이 가능하다.

 

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
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 p6593 {
    static int moveY[] = {-1,0,1,0,0,0};
    static int moveX[] = {0,1,0,-1,0,0};
    static int moveZ[] = {0,0,0,0,1,-1};
    static int L,R,C;
    static char arr[][][];
    static int map[][][];
    static boolean visit[][][],check=false;
    static Po start, end;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            check = false;
            StringTokenizer st = new StringTokenizer(br.readLine());
            if(!st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            
            L = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            if(L==0 && R==0 && C==0) {
                break;
            }
            arr = new char[L][R][C];
            map = new int[L][R][C];
            visit = new boolean[L][R][C];
            
            for(int l=0; l<L; l++) {
                for(int r=0; r<R; r++) {
                    String str = br.readLine();
                    
                    if(str.equals("")) 
                        str = br.readLine();
                        
                    for(int c=0; c<C; c++) {
                        char ch = str.charAt(c);
                        if(ch == 'S') {
                            start = new Po(c,r,l);
                        }else if(ch == 'E') {
                            end = new Po(c,r,l);
                        }
                        arr[l][r][c] = ch;
                    }
                }
            }
            
            bfs(start);
            if(!check) {
                System.out.println("Trapped!");
            }
        }
        
        
    }
    public static void bfs(Po p) {
        Queue<Po> queue = new LinkedList<>();
        queue.add(p);
        visit[p.z][p.y][p.x] = true;
        
        while(!queue.isEmpty()) {
            Po tmp = queue.poll();
            if(tmp.x == end.x && tmp.y == end.y && tmp.z == end.z) {
                
                System.out.println("Escaped in "+map[tmp.z][tmp.y][tmp.x]+" minute(s).");
                check = true;
                return;
            }
            
            for(int d=0; d<6; d++) {
                int newX = tmp.x + moveX[d];
                int newY = tmp.y + moveY[d];
                int newZ = tmp.z + moveZ[d];
                
                if(0<=newX && newX<C && 0<=newY && newY<R && 0<=newZ && newZ<L && !visit[newZ][newY][newX]) {
                    if(arr[newZ][newY][newX]!='#') {
                        visit[newZ][newY][newX] = true;
                        map[newZ][newY][newX] = map[tmp.z][tmp.y][tmp.x] + 1;
                        queue.add(new Po(newX,newY,newZ));
                    }
                }
            }
        }
        
    }
    public static class Po{
        int x;
        int y;
        int z;
        public Po(int x,int y,int z) {
            this.x=x;
            this.y=y;
            this.z=z;
        }
    }
}
 
 cs

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

#백준_1592 영식이와 친구들 - Java 자바  (0) 2020.02.16
#백준_1613 역사 - Java 자바  (0) 2020.02.16
#백준_1389 케빈 베이컨의 6단계 법칙  (0) 2020.02.15
#백준_2668 숫자고르기 - Java 자바  (0) 2020.02.14
#백준_2644 촌수계산 - Java 자바  (0) 2020.02.14

# 유형 : 그래프 탐색, 최단경로, 플로이드 와샬

# 문제를 잘 보면 그래프에서 모든 정점 사이의 최단 경로를 구하는 문제라는 것을 알 수 있다. 이 때 떠오르는 알고리즘은 플로이드 와샬 알고리즘이다. 플로이드 와샬은 거쳐가는 정점을 기준으로 알고리즘을 수행하는 특징을 가지고 있고, 다이나믹 프로그래밍 기반이다. BFS로도 풀 수 있을 것 같지만 우선 플로이드 와샬로 문제를 해결해보았다. 시간복잡도는 O(V^3)이다.

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;
import java.util.StringTokenizer;
 
public class p1389 {
    static int N,M;
    static int arr[][];
    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());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][N];
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                arr[i][j] = 999999;
        
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            arr[u-1][v-1] = 1;
            arr[v-1][u-1] = 1;
        }
        floyd_warshall();
        
        int min = 999999;
        int index = 0;
        for(int i=0; i<N; i++) {
            int sum = 0;
            for(int j=0; j<N; j++) {
                sum += arr[i][j];
            }
            if(min > sum) {
                min = sum;
                index = i;
            }
//            System.out.println(sum);
        }
        System.out.println(index+1);
    }
    
    public static void floyd_warshall() {
        for(int k=0; k<N; k++) {
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
                }
            }
        }
    }
}
 
 cs

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

#백준_1613 역사 - Java 자바  (0) 2020.02.16
#백준_6593 상범 빌딩 - Java 자바  (0) 2020.02.15
#백준_2668 숫자고르기 - Java 자바  (0) 2020.02.14
#백준_2644 촌수계산 - Java 자바  (0) 2020.02.14
#백준_10026 적록색약 - Java 자바  (0) 2020.02.13

# 유형 : 그래프탐색, 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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p2668 {
    static int N;
    static int arr[];
    static int result=0;
    static boolean visit[],cycle[];
    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];
        visit = new boolean[N+1];
        cycle = new boolean[N+1];
        
        for(int i=1; i<=N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++)
                visit[j] = cycle[j];
            dfs(i,arr[i]);
        }
        System.out.println(result);
        for(int i=1; i<=N; i++) {
            if(cycle[i])
                System.out.println(i);
        }
    }
    
    public static boolean dfs(int start_val, int arr_val) {
//        System.out.println(start_val + " "+arr_val);
        if(visit[arr_val] == true)
            return false;
        
        visit[arr_val] = true;
        
        if(start_val == arr_val || dfs(start_val, arr[arr_val])) {
            result++;
//            System.out.println(start_val+" "+"cehck"+ arr_val);
            cycle[arr_val] = true;
            return true;
        }
        return false;
    }
}
 
 cs

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

#백준_6593 상범 빌딩 - Java 자바  (0) 2020.02.15
#백준_1389 케빈 베이컨의 6단계 법칙  (0) 2020.02.15
#백준_2644 촌수계산 - Java 자바  (0) 2020.02.14
#백준_10026 적록색약 - Java 자바  (0) 2020.02.13
#백준_1325 효율적인 해킹 - Java 자바  (0) 2020.02.12

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

# 간단한 BFS 문제. 큐에 넣을 때마다 촌수를 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
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 p2644 {
    static boolean check = false;
    static int N,M;
    static int start,end;
    static int arr[][];
    static boolean visit[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine());
        
        arr = new int[N+1][N+1];
        visit = new boolean[N+1];
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            arr[u][v] = 1;
            arr[v][u] = 1;
        }
        
        bfs(start);
        if(!check) {
            System.out.println(-1);
        }
    }
    
    public static void bfs(int begin) {
        Queue<Point> queue = new LinkedList<Point>();
        visit[begin] = true;
        queue.add(new Point(begin, 0));
        
        while(!queue.isEmpty()) {
            Point po = queue.poll();
            
            if(po.x == end) {
                System.out.println(po.y);
                check = true;
                return;
            }
            
            for(int i=1; i<=N; i++) {
                if(arr[po.x][i]==1 && !visit[i]) {
                    visit[i] = true;
                    queue.add(new Point(i, po.y+1));
                }
            }
        }
    }
}
 
 cs

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

#백준_1389 케빈 베이컨의 6단계 법칙  (0) 2020.02.15
#백준_2668 숫자고르기 - Java 자바  (0) 2020.02.14
#백준_10026 적록색약 - Java 자바  (0) 2020.02.13
#백준_1325 효율적인 해킹 - Java 자바  (0) 2020.02.12
#백준_7562 나이트의 이동 - Java 자바  (0) 2020.02.11

# 유형 : 탐색, 그래프

# 방법은 여러가지 있을텐데, 그냥 귀찮아서 입력받을때 적록색약인 사람을 위한 배열을 하나 더 만들었다.

그다음 BFS를 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.awt.Point;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
 
public class p10026 {
    static int N;
    static char arr[][], map[][];
    static boolean visit[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static int cnt1,cnt2=0;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        arr = new char[N][N];
        map = new char[N][N];
        visit = new boolean[N][N];
        
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<N; j++) {
                char ch = str.charAt(j);
                if(ch=='G') {
                    arr[i][j] = ch;
                    map[i][j] = 'R';
                }else {
                    arr[i][j] = ch;
                    map[i][j] = ch;
                }
            }
        }
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visit[i][j]) {
                    bfs(i,j,arr);
                    cnt1++;
                }
            }
        }
        visit = new boolean[N][N];
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(!visit[i][j]) {
                    bfs(i,j,map);
                    cnt2++;
                }
            }
        }
        System.out.println(cnt1+" "+cnt2);
    }
    
    public static void bfs(int i, int j, char ar[][]) {
        Queue<Point> queue = new LinkedList<Point>();
        char ch = ar[i][j];
        queue.add(new Point(j,i));
        visit[i][j] = true;
        while(!queue.isEmpty()) {
            Point p = queue.poll();
            int x = p.x;
            int y = p.y;
            
            for(int d=0; d<4; d++) {
                int newX = x + moveX[d];
                int newY = y + moveY[d];
                
                if(0<=newX && newX<N && 0<=newY && newY<N && !visit[newY][newX]) {
                    if(!visit[newY][newX] && ar[newY][newX]==ch) {
                        visit[newY][newX] = true;
                        queue.add(new Point(newX, newY));
                    }
                }
            }
        }
    }
}
 
 cs

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

#백준_2668 숫자고르기 - Java 자바  (0) 2020.02.14
#백준_2644 촌수계산 - Java 자바  (0) 2020.02.14
#백준_1325 효율적인 해킹 - Java 자바  (0) 2020.02.12
#백준_7562 나이트의 이동 - Java 자바  (0) 2020.02.11
#백준_2573 빙산 - Java 자바  (0) 2020.02.10

# 유형 : 탐색, 그래프, BFS, DFS

# 너무 BFS로만 해결하는 것 같아서 DFS로 접근해보았다... 근데 아무리 풀어도 시간초과 발생. 다른 블로그 글 참고하면서 보는데 다 같은 로직인데 게시글을 올려놨길래 잘 못 짠거같아서 계속 수정해보았으나 시간초과. 다른 분들 코드 복붙을 했더니.. 시간초과.. 심지어 같은 로직으로 C++ 코드로 제출했더니 통과..

결국은 BFS로 풀었다. 자바 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
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
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p1325 {
    static int N,M;
    static boolean visit[];
    static int arr[];
    static ArrayList<Integer> arrList[]; 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arrList = new ArrayList[N+1];
        arr = new int[N+1];
        
        for(int i=1; i<=N; i++)
            arrList[i] = new ArrayList<>();
        
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            arrList[u].add(v);
        }
        
        for(int i=1; i<=N; i++) {
            visit = new boolean[N+1];
            bfs(i);
        }
        
        int max = 0;
        
        for(int i=1; i<=N; i++) {
            max = Math.max(max, arr[i]);
        }
        StringBuffer sb = new StringBuffer();
        for(int i=1; i<=N; i++) {
            if(arr[i] == max)
                sb.append(i+" ");
        }
        System.out.println(sb.toString());
    }
    public static void bfs(int index) {
        
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(index);
        visit[index] = true;
        
        while(!queue.isEmpty()) {
            int val = queue.poll();
            for(int i=0; i<arrList[val].size(); i++) {
                int v = arrList[val].get(i);
                if(!visit[v]){
                    visit[v] = true;
                    arr[v]++;
                    queue.add(v);
                }
            }
        }
    }
    public static void dfs(int index) {
        // TODO Auto-generated method stub
        visit[index] = true;
        
        for(int i=0; i<arrList[index].size(); i++) {
            if(!visit[arrList[index].get(i)]) {
                arr[arrList[index].get(i)]++;
                dfs(arrList[index].get(i));
            }
        }
    }
}
 
 cs

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

#백준_2644 촌수계산 - Java 자바  (0) 2020.02.14
#백준_10026 적록색약 - Java 자바  (0) 2020.02.13
#백준_7562 나이트의 이동 - Java 자바  (0) 2020.02.11
#백준_2573 빙산 - Java 자바  (0) 2020.02.10
#백준_1062 가르침 - Java 자바  (0) 2020.02.10

+ Recent posts

티스토리툴바