문제 보기 >> [SWEA] 2383. 점심식사 시간





1. 입력을 받을때 사람의 위치와 계단의 위치를 각각의 ArrayList에 저장.



2. whichStair(int len) 메소드 - 중복순열

각각의 사람이 어떤 계단을 이용할 것인지 중복순열 코드를 돌려서 모든 케이스를 다 확인할 수 있게 한다.

중복순열이 완성되면, 우선순위큐에 데이터를 add.


우선순위 큐의 타입으로 pair2 클래스를 선언해서 사용했다.

**pair2 클래스

각 사람에 대해 할당된 시간과 이용할 계단, 그리고 상태를 저장하기 위한 클래스.

status ==> -1 : 계단에 도착하기 전 // 0 : 계단에 도착은 했지만 대기중. // 1 : 계단에 올라가 있음.  

하단 pair2 클래스 선언 부분에서 Compare부분을 보면, 기본적으로 시간이 짧은 순으로 정렬되고 시간이 같을땐 status를 기준으로 정렬했다. 

이 compare는 우선순위큐에서 정렬되는 기준을 정하기 위함이다.

같은 시간내에서 계단에 올라가 있는 사람을 먼저 pop 하기위해서 시간이 같을때에는, status가 큰 수를 우선적으로 정렬되도록 했다.



3. goStair() 메소드

각각의 사람이 어떤 계단을 사용할것인지 완성이 되었다면, goStair() 메소드에서 실제로 계단에 보내본다.

inStair 배열은 각각의 계단을 몇명의 사람이 이용하고 있는지 카운트해주는 배열이다.


우선순위큐(pq)에서 시간이 짧은사람(계단에 있는사람->대기->도착 순으로 pop) 부터 확인해본다.

가장 바깥 while문은 시간에 대한 while문이다 min이 1씩 증가한다.

min이 일정 시간일때 안쪽 while을 돌면서 해당 시간인 사람을 pop 해서 검사한다.


status 가 1이 아니면 아직 계단을 이용하지 못한 사람이고, 그 중 -1이면 이제 계단에 도착한 사람이므로 계단 이용전 필수 대기시간인 +1을 더 해준다.

시간과 상태를 갱신해 다시 pq에 add해주고 계단이용자수를 증가시켜준다.

** 여기서 ntime이 의미하는 것은 시작점부터 계단까지 시간 + 대기시간 + 계단 이용시간이다.

즉, 계단 이용이 끝날때까지는 큐에서 나올 수 없다.


만약 계단이 포화상태라 갈수 없다면 시간만 +1 해주고, status는 0으로 다시 add한다.



status가 1이면 계단에 올라있는 상태에서 시간이 다 지난것을 의미하기 떄문에 해당 inStair을 감소시켜주고 큐에 다시 add 하지 않는다.


4. q가 비게되면 최소값을 갱신해준다.



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
132
133
134
135
136
137
138
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
//SWEA :: 2383 점심 식사시간 
//2019-04-04
public class Solution2383_점심식사시간 {
    private static int[][] map;
    private static int N, ans;
    private static ArrayList<pair> ppl;
    private static ArrayList<pair> stair;
    private static int[] set;
    private static PriorityQueue<pair2> pq;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            ppl = new ArrayList<>();
            stair = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (map[i][j] == 1)
                        ppl.add(new pair(i, j));
                    if (map[i][j] > 1)
                        stair.add(new pair(i, j));
                }
            } /// input
            set = new int[ppl.size()];
            ans = Integer.MAX_VALUE;
            whichStair(0);
 
            System.out.println("#" + tc + " " + ans);
        } // end of tc
    }// end of main
 
    public static void whichStair(int len) {
        if (len == ppl.size()) { // 사람의 명수만큼 계단 고르기 --> 중복순열
            // System.out.println(Arrays.toString(set));
            pq = new PriorityQueue<>();
            
            for (int i = 0; i < len; i++) {
                int py = ppl.get(i).y;
                int px = ppl.get(i).x;
                int sy = stair.get(set[i]).y;
                int sx = stair.get(set[i]).x;
                int t = Math.abs(py - sy) + Math.abs(px - sx);
                pq.add(new pair2(t, set[i], -1));
            }
            goStair();
            return;
        }
 
        for (int i = 0; i < stair.size(); i++) {
            set[len] = i; // 인덱스 저장
            whichStair(len + 1);
        }
    } // end of whichStair
 
    public static void goStair() {
        /*
         * pair2의 status -1: 계단에 도착 전 0: 계단에 도착은 했지만 대기중. 1:계단에 올라가 있음
         */
        int min = 0;
        int[] inStair = new int[stair.size()]; // idx번째 계단에 몇명의 사람이 있는지 확인.
        while (!pq.isEmpty()) {
            min++;
 
            while (!pq.isEmpty()) {
                pair2 front = pq.peek();
                if (front.time != min)
                    break;
                pq.poll();
                int mystair = front.stair;
                if (front.status != 1) { // 계단 아직 안감.
                    //계단을 내려갈 수 있나?
                    if (inStair[mystair] < 3) { // 갈 수 있으면
                        int ntime = 0;
                        if (front.status == -1) { //계단에 최초 도착이면 1분 대기한다.
                            ntime = front.time + 1 + map[stair.get(mystair).y][stair.get(mystair).x];
                        } else if (front.status == 0) { //이전에 도착해 대기하고있었으면 바로 계단에 간다.
                            ntime = front.time + map[stair.get(mystair).y][stair.get(mystair).x];
                        }
                        pq.add(new pair2(ntime, front.stair, 1));
                        inStair[mystair]++;
                    } else { // 계단이 포화 상태라 갈 수 없다면.
                        pq.add(new pair2(front.time + 1, front.stair, 0));
                    }
                } else { // front.status == 1//계단에 있는 상태.
                    inStair[mystair]--;
                }
            }
        }
        ans = ans > min ? min : ans;
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    } // end of pair
 
    static class pair2 implements Comparable<pair2> {
        int time;
        int stair;
        int status;
 
        public pair2(int time, int stair, int status) {
            super();
            this.time = time;
            this.stair = stair;
            this.status = status;
        }
 
        @Override
        public int compareTo(pair2 o) {
            // TODO Auto-generated method stub
            if (this.time == o.time) {
                return o.status - this.status;
            } else {
                return this.time - o.time;
            }
        }
 
    }
}// end of class
cs


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 15685. 드래곤 커브  (5) 2019.04.09
[BOJ] 1938 통나무 옮기기  (0) 2019.04.05
[SWEA] 1949. 등산로 조성  (0) 2019.04.01
[BOJ] 1805. 나무자르기  (4) 2019.03.22
[BOJ] 14502 : 연구소  (2) 2019.03.12

문제 >> [SWEA] 1949. 등산로 조성






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
mport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
//SWEA :: 1949 등산로조성
//2019-04-01
public class Solution1949_등산로조성 {
    private static int[][] map;
    private static boolean[][] visit;
    private static int N;
    private static int K;
    private static ArrayList<pair> top;
    private static int bottom;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken()); // 최대 K만큼 한 번 지형을 깎는다
 
            map = new int[N][N];
            top = new ArrayList<>();
            int max = -1;
            bottom = 21;
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (max < map[i][j]) {
                        max = map[i][j];
                        top.clear();
                        top.add(new pair(i, j));
                    } else if (max == map[i][j]) {
                        top.add(new pair(i, j));
                    }
                    bottom = bottom > map[i][j] ? map[i][j] : bottom;
                }
            } ////// input
 
            ans = -1;
            for (pair p : top) {
                visit = new boolean[N][N];
                dfs(p.y, p.x, 1, false);
 
            }
 
            System.out.println("#" + tc + " " + ans);
        } // end of tc
    }// end of main
 
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static int ans;
 
    private static void dfs(int y, int x, int len, boolean cut) {
        // cut이 true 면 공사를 했다.
 
        visit[y][x] = true;
 
        ans = ans < len ? len : ans;
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || visit[ny][nx])
                continue;
            if (map[ny][nx] < map[y][x]) {
                dfs(ny, nx, len + 1, cut);
            } else { // 같거나 높으면
                if (!cut) { // cut이 false면 아직 공사를 안한 상태
                    for (int k = 1; k <= K; k++) {
                        int tmp = map[ny][nx];
                        map[ny][nx] -= k;
                        if (map[ny][nx] < map[y][x])
                            dfs(ny, nx, len + 1, true);
                        map[ny][nx] = tmp;
                    }
                }
            }
            visit[ny][nx] = false;
        }
 
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
 
    }
}
cs

dfs와 약간의 백트래킹을 이용해 풀었습니다 ~~~~~

저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 1938 통나무 옮기기  (0) 2019.04.05
[SWEA] 2383. 점심식사 시간  (5) 2019.04.04
[BOJ] 1805. 나무자르기  (4) 2019.03.22
[BOJ] 14502 : 연구소  (2) 2019.03.12
[BOJ] 17070 : 파이프 옮기기 1  (0) 2019.03.12
문제 >> [BOJ] 1805. 나무자르기




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
jaimport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
//BOJ :: 1805 나무자르기
//2019-03-22
 
public class Main2805 {
    static int N;
    static long[] arr;
    static long M,ans;
    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 = Long.parseLong(st.nextToken());//상근이가 필요한 나무의 길이
        
        ans = Long.MIN_VALUE;
        arr = new long [N];
        st = new StringTokenizer(br.readLine(), " ");
        long maxh = Long.MIN_VALUE;
        
        for(int i=0;i<N;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            maxh = maxh<arr[i]? arr[i] : maxh;
        } 
        /////////////////input
        
        bsearch(0, maxh);
        System.out.println(ans);
        
        
    }
    static boolean flag = false;
    public static void bsearch(long start, long end) {
        //if(flag) return;
        if(start>end) {
            return ;
        }
        
        long mid = (start+end)/2; //현재 절단기 높이
        
        //종료조건
        long sum = 0;
        for(int i=0;i<N;i++) {
            long tmp = arr[i]-mid;
            sum += ((tmp>0)? tmp : 0);
        }
        //sum이 M보다 작으면 높이를 낮춘다.
        //sum이 M보다 크면 높이를 높인다.
        if(sum>=M) {
            ans = ans < mid? mid:ans;
            bsearch(mid+1, end);
        }
        else if(sum<M) {
            bsearch(start, mid-1);
        }
        return;
    }
}
 
cs


모든 데이터 타입을 long 으로 해주어야 합니다 

저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[SWEA] 2383. 점심식사 시간  (5) 2019.04.04
[SWEA] 1949. 등산로 조성  (0) 2019.04.01
[BOJ] 14502 : 연구소  (2) 2019.03.12
[BOJ] 17070 : 파이프 옮기기 1  (0) 2019.03.12
[SWEA] 1761 : 프로세서 연결하기  (0) 2019.03.08
문제 >> [BOJ] 14502 : 연구소





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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution14502_연구소 {
    private static int N, M, safe, max;
    static int[][] origin_map;
    static int[][] map;
    static Queue<pair> virus;
    static ArrayList<pair> walls;
    static pair[] selectedWall;
 
    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());
        origin_map = new int[N][M];
        walls = new ArrayList<pair>();
        max = -1;
        virus = new LinkedList<pair>();
        // 0은 빈칸, 1은 벽, 2는 바이러스
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                origin_map[i][j] = Integer.parseInt(st.nextToken());
                if (origin_map[i][j] == 2)
                    virus.add(new pair(i, j));
                if (origin_map[i][j] == 0)
                    walls.add(new pair(i, j));
 
            }
        }
 
        selectedWall = new pair[3];
        setWall(0, 0);
        System.out.println(max);
    } // end of main
 
    // 벽 선택하기 (3개)
    public static void setWall(int len, int k) {
        if (len == 3) {
 
            mapcopy();
 
            for (int i = 0; i < 3; i++) {
 
                pair p = selectedWall[i];
                map[p.y][p.x] = 1; // 벽 세우기
                safe--;
            }
 
            spreadVirus();
 
            return;
        }
 
        for (int i = k; i < walls.size(); i++) {
            selectedWall[len] = walls.get(i);
            setWall(len + 1, i + 1);
        }
    }
 
    public static void spreadVirus() { // 바이러스 퍼트리기
        int[] dy = { -1, 1, 0, 0 };
        int[] dx = { 0, 0, -1, 1 };
 
        while (!virus.isEmpty()) {
            pair p = virus.poll();
 
            for (int i = 0; i < 4; i++) {
 
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];
                if (ny < 0 || ny > N - 1 || nx < 0 || nx > M - 1 || map[ny][nx] != 0)
                    continue;
                map[ny][nx] = 2;
                safe--;
                virus.add(new pair(ny, nx));
 
            }
        }
 
        if (max < safe)
            max = safe;
 
    }
 
    public static void mapcopy() {
        virus.clear();
        safe = 0;
        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = origin_map[i][j];
                if (origin_map[i][j] == 2)
                    virus.add(new pair(i, j));
                if (origin_map[i][j] == 0)
                    safe++;
            }
        }
    }
 
    public static class pair {
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
 
        int y;
        int x;
 
    }
}
 
cs


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[SWEA] 1949. 등산로 조성  (0) 2019.04.01
[BOJ] 1805. 나무자르기  (4) 2019.03.22
[BOJ] 17070 : 파이프 옮기기 1  (0) 2019.03.12
[SWEA] 1761 : 프로세서 연결하기  (0) 2019.03.08
[SWEA] 5656 : [모의 SW 역량테스트] 벽돌 깨기  (1) 2019.03.07
문제 >> [BOJ] 17070 : 파이프 옮기기 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
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//BOJ :: 17070 파이프 옮기기1
//2019-03-12
 
public class Solution17070_파이프옮기기1 {
    static int N;
    static int[][] map;
    static boolean[][] visit;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visit = new boolean[N][N];
        
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<N;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        cnt = 0;
        dfs(0,1,1);
        
        System.out.println(cnt);
        
    } // end of main
    static int cnt;
    static int[] dy = {1,0, 1};
    static int[] dx = {0,1, 1}; //아래 오른쪽 대각선
    public static void dfs(int y,int x, int type){
        //type
        //0 : 세로
        //1 : 가로
        //2 : 대각선
        
        //visit[y][x]=true;
        System.out.println(y+","+x);
        if(y==N-1 && x==N-1) { //도착
            System.out.println("도착");
            cnt++;
            return;
        }
        
        int[] Dir = getDir(type);
        
        for(int i=0;i<Dir.length;i++) {
 
            int ny = y+dy[Dir[i]];
            int nx = x+dx[Dir[i]];
            
            if(ny<0 || ny>N-1 || nx<0 || nx>N-1 || map[ny][nx]!=0) continue;
            //대각선으로 이동시 주변 4칸이 확보되어 있어야 한다.
            if(Dir[i]==2 && (map[y][x+1]!=0||map[y+1][x]!=0)) continue; 
            
            
            dfs(ny,nx,Dir[i]);
            
        }
        
    }
    
    public static int[] getDir(int type) {
        
        //type
        //0 : 세로
        //1 : 가로
        //2 : 대각선
        
        //아래 오른쪽 대각선
        if(type == 0) { //세로
            int[] ret = {0,2};
            return ret;
        } 
        if(type == 1) { //가로
            int[] ret = {1,2};
            return ret;
        }
        if(type ==2) {
            int[] ret = {0,1,2};
            return ret;
        }
        return null;
    }
    
}
 
cs


파이프가 현재 놓아져 있는 상태 (가로 / 세로/ 대각선) 에 따라 이동할 수 있는 방향이 다르기 때문데

각각의 케이스를 구해주는 메소드를 구현했습니다 ( getDir() )


나머지는 dfs로 구현했습니다.



저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 1805. 나무자르기  (4) 2019.03.22
[BOJ] 14502 : 연구소  (2) 2019.03.12
[SWEA] 1761 : 프로세서 연결하기  (0) 2019.03.08
[SWEA] 5656 : [모의 SW 역량테스트] 벽돌 깨기  (1) 2019.03.07
[SWEA] 1258 : [S/W 문제해결 응용] 7일차 - 행렬찾기  (0) 2019.03.07
문제 >> 1761 프로세서 연결하기

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
//SWEA :: 1761 프로세서 연결하기
//2019-03-08
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Solution1767_2 {
 
    static int[][] map;
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };// 상하좌우
    static int coreCnt, N, coreMax, lineMin;
    static ArrayList<pair> core;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine().trim());
 
        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(bf.readLine().trim());
 
            map = new int[N][N];
            core = new ArrayList<>();
            coreCnt = 0; //전체 코어의 개수
            coreMax = Integer.MIN_VALUE;
            lineMin = Integer.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (map[i][j] == 1) {
                        if (i == 0 || i == N - 1 || j == 0 || j == N - 1)
                            continue; //가장자리 코어는 버린다
 
                        coreCnt++;
                        core.add(new pair(i, j)); //코어의 위치를 core리스트에 저장 
                    }
                }
            } // input
 
            setCore(0, 0, 0);
            System.out.println("#" + tc + " " + lineMin);
        } // end of tc
    } // end of main
 
    public static void setCore(int coreIdx, int sucCore, int lineLen) {
        if (coreIdx == coreCnt) { //모든 코어를 다 순회했을 때
            if (coreMax < sucCore) {
                coreMax = sucCore;
                lineMin = lineLen;
            } else if (coreMax == sucCore) {
                lineMin = lineMin > lineLen ? lineLen : lineMin;
            }
            return;
        }
 
        for (int i = 0; i < 4; i++) {
            int ret = setLine(coreIdx, i);
            if (ret == -1) { // 전선 설치 실패
                setCore(coreIdx + 1, sucCore, lineLen);
            } else { // 전선 설치 성공
                setCore(coreIdx + 1, sucCore + 1, lineLen + ret);
                
                //Backtracking
                //전선 회수
                int ny = core.get(coreIdx).y;
                int nx = core.get(coreIdx).x;
                while (true) {
                    ny += dy[i];
                    nx += dx[i];
                    if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1)
                        break; // 전원에 도달했을 경우
                    map[ny][nx] = 0; // 설치했던 전선을 회수한다.
 
                }
 
            }
        }
    }
 
    public static int setLine(int coreIdx, int dir) {
        ArrayList<pair> list = new ArrayList<>();
        pair cp = core.get(coreIdx);
        int ny = cp.y;
        int nx = cp.x;
        int lineLen = 0;
        while (true) {
            ny += dy[dir];
            nx += dx[dir];
            if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1)
                break; // 전원에 도달했을 경우
            if (map[ny][nx] != 0)
                return -1; // 전선 설치 실패
            list.add(new pair(ny, nx)); // 전선 설치할 위치 저장
 
            lineLen++;
        }
 
        // 전원 도달에 성공했을 때만 전선을 설치한다.
        for (pair p : list) {
            map[p.y][p.x] = 2;
        } // 전선 설치
 
        return lineLen; // 전선 길이 return
    } // end of setLine
 
    public static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
 
    }
 
}
 
cs


처음엔 각 코어의 전선 설치 방향에 대한 모든 경우를 중복조합을 이용해 배열에 저장후
배열 값에 따라 전선을 설치하고, max/min 값을 갱신해가며 최종 답을 구하려고 했지만 시간 초과가 났다.

이유는 다음과 같다.
[0, 1, 2, 3] 을 각각 [상, 하, 좌, 우] 라고 생각한다면

코어가 7개 일때
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1]
.
.
[3, 3, 3, 3, 3, 3, 3]
의 모든 경우에 대해 전선을 설치해볼 것이다.




하지만 같은 로직을 dfs를 이용해 구현한다면


[0, 0, 0, 0, 0, 0, 1] 해당하는 경우를 구한다음
     
     
[0, 0, 0, 0, 0, 0, 2] 를 구할때,

앞에 겹치는 부분인 [0, 0, 0, 0, 0, 0, X] 에 대한 부분은 볼 필요 없다.


즉 1방향으로 설치했던 전선을 회수하고
2 방향으로만 전선을 설치해보면 된다.


(내가 원래 짰던 코드에서는 앞의 0도 다시 순회를 했던 것 ..)



같은 완탐이어도 경우를 미리 구해놓고 하면 중복되는 케이스가 많아서 시간초과가 날수 있다는 것을 깨달았다 .

겹치는 케이스가 많다면 미리 구해놓지 말고 그때그때 dfs로 탐색하는 것이 시간을 줄일 수 있는 방법이다.

저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 14502 : 연구소  (2) 2019.03.12
[BOJ] 17070 : 파이프 옮기기 1  (0) 2019.03.12
[SWEA] 5656 : [모의 SW 역량테스트] 벽돌 깨기  (1) 2019.03.07
[SWEA] 1258 : [S/W 문제해결 응용] 7일차 - 행렬찾기  (0) 2019.03.07
[BOJ] 9663 : N-Queen  (0) 2019.03.07

문제 >> 5656 : [모의 SW 역량테스트] 벽돌 깨기



1. 구슬 쏠 곳 선택하기

rperm() : 중복순열 이용 



2. 벽돌 깨트리기

brick() : bfs 이용


3. 벽돌 밑으로 당기기

removeEmpty() : Queue 이용

큐에 0이 아닌 값을 다 옮긴 후 밑부터 다시  삽입.



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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
//SWEA :: 5656 [모의 SW 역량테스트] 벽돌 깨기
//2019-03-07
public class Solution5656 {
    static int[][] origin_map;
    static int[][] map;
    static int[] set;
    static int[] origin_top;
    static int[] top;
    static HashSet<Integer> hs;
    static int N, W, H;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };
    static int min;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
            N = Integer.parseInt(st.nextToken()); // 벽돌 개수
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            min = Integer.MAX_VALUE;
            origin_map = new int[H][W];
            map = new int[H][W];
            set = new int[N]; // 벽돌을 떨어트릴 idx를 저장하는 배열
            hs = new HashSet<Integer>();
            
            // 벽돌의 높이를 저장하는 배열 : W번째 벽돌의 높이는 top[W];
            origin_top = new int[W];
 
            Arrays.fill(origin_top, -1);
 
            for (int i = 0; i < H; i++) {
                st = new StringTokenizer(bf.readLine(), " ");
                
                //i번째 줄의 벽돌의 최고높이 좌표 == (top[j],j)
                //벽돌이 있고, top[i] == -1 (아직 비어있으면 ) top을 갱신해준다.
                for (int j = 0; j < W; j++) {
                    origin_map[i][j] = Integer.parseInt(st.nextToken());
                    if (origin_map[i][j] != 0 && origin_top[j] == -1) {
                        origin_top[j] = i;
                    }
                }
            } // input
 
            rperm(0);
            
            System.out.println("#"+tc+" "+min);
        } // end of tc
    }// end of main
 
    public static void mapcopy() {
        map = new int[H][W];
        top = new int[W];
        
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                map[i][j] = origin_map[i][j];
            }
        }
        
        for(int i=0;i<W;i++) {
            top[i] = origin_top[i];
        }
    }
 
    // wCn 수행 , 벽돌을 떨어트릴 곳을 결정한다.
    public static void rperm(int len) {
        if (len == N) { // N개의 중복 순열이 완료되었을 때 --> set 배열에 저장되있음.
            mapcopy(); 
            for (int j = 0; j < N; j++) {
                // 벽돌을 떨어트릴 좌표 (y,x)
                if(top[set[j]]==-1||top[set[j]]>H-1) continue;
                brick(top[set[j]], set[j]);
                removeEmpty();
            }
            
            int cnt = 0;
            for(int i=0;i<H;i++) {
                for(int j=0;j<W;j++) {
                    if(map[i][j]!=0) cnt++;
                }
            }
            min = min > cnt ? cnt : min;
            
            return;
        }
 
        for (int i = 0; i < W; i++) {
            set[len] = i;
            rperm(len + 1);
        }
    }
 
    // x위치에 벽돌을 떨어트린다.
    public static void brick(int y, int x) {
        Queue<pair> q = new LinkedList<>();
        q.add(new pair(y, x));
        while (!q.isEmpty()) {
            pair p = q.poll();
            int py = p.y;
            int px = p.x;
            int pw = map[py][px];
 
            map[py][px] = 0; // 벽돌 깨기
            hs.add(px); // 빈공간 제거를 위해 x좌표 저장
 
            if (pw == 1) continue;
 
            for (int i = 0; i < 4; i++) {
                int ny = py;
                int nx = px;
                for (int j = 0; j < pw - 1; j++) {
                    ny += dy[i];
                    nx += dx[i];
                    if (ny < 0 || ny > H - 1 || nx < 0 || nx > W - 1 || map[ny][nx] == 0)
                        continue;
                    q.add(new pair(ny, nx));
                }
            }
        }
    } // end of brick
 
    public static void removeEmpty() {
        Queue<Integer> tmpQ = new LinkedList<Integer>();
        Iterator<Integer> it = hs.iterator();
        while (it.hasNext()) {
            int xIdx = it.next(); // 확인해야 할 x index
 
            for (int i = H - 1; i >= top[xIdx]; i--) {
                if (map[i][xIdx] != 0)
                    tmpQ.add(map[i][xIdx]);
                    map[i][xIdx]=0;
            }
            int tmpSize = tmpQ.size();
            top[xIdx] = H - tmpSize; // 벽돌을 밑으로 땡긴 후 최상위 좌표.
            for (int i = 0; i < tmpSize; i++) {
                map[H - 1-i][xIdx] = tmpQ.poll();
            }
        }
        hs.clear();
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    }
}
 
cs


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 17070 : 파이프 옮기기 1  (0) 2019.03.12
[SWEA] 1761 : 프로세서 연결하기  (0) 2019.03.08
[SWEA] 1258 : [S/W 문제해결 응용] 7일차 - 행렬찾기  (0) 2019.03.07
[BOJ] 9663 : N-Queen  (0) 2019.03.07
[SWEA] 7236 : 저수지의 물의 총 깊이 구하기  (1) 2019.03.07

문제 >> [SWEA] 1258 : [S/W 문제해결 응용] 7일차 - 행렬찾기

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
//SWEA :: 1258 [S/W 문제해결 응용] 7일차 - 행렬찾기
//2019-03-07
public class Solution1258 {
    static int[][] map;
    static int n;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(bf.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
 
            n = Integer.parseInt(bf.readLine());
            map = new int[n][n];
 
            map = new int[n][n];
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
                for (int j = 0; j < n; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            } // input
            
            
            ArrayList<pair> list = new ArrayList<>();
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j] != 0) {
                        //행열 크기 계산을 위한 변수
                        endY = -1;
                        endX = -1;
                        dfs(i, j);
                        list.add(new pair(endY-i+1, endX-j+1));
                        cnt++;
                    }
                }
            }
            System.out.print("#" + tc + " " + cnt);
            
            list.sort(null);
            for(pair p : list) {
                System.out.print(" "+p.y+" "+p.x);
            }
            
            System.out.println();
        } // end of tc
 
    }// end of main
 
    static int endY, endX;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
 
    public static void dfs(int y, int x) {
        map[y][x] = 0; // visit check
        endY = endY < y ? y : endY;
        endX = endX < x ? x : endX;
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1 || map[ny][nx]==0)
                continue;
 
            dfs(ny, nx);
        }
    }
 
    static class pair implements Comparable<pair> {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
 
        @Override
        public int compareTo(pair o) {
            int oMul = o.y * o.x;
            int thisMul = this.y * this.x;
 
            if (oMul == thisMul) {
                return this.y - o.y;
            } else {
                return thisMul - oMul;
            }
        }
 
    }
}
 
cs



＊행렬의 크기 구하는 방법.


dfs 돌때마다 y와 x의 최대값을 갱신해 주었습니다. (endY, endX)

재귀호출이 끝나고 main 으로 돌아왔을때 dfs 시작점이었던 (i,j)와 (endY, endX) 의 차를 이용해 행과 열의 크기를 구해주었고

해당 값을 pair라는 클래스타입으로 list에 넣은후 sort 했습니다.


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[SWEA] 1761 : 프로세서 연결하기  (0) 2019.03.08
[SWEA] 5656 : [모의 SW 역량테스트] 벽돌 깨기  (1) 2019.03.07
[BOJ] 9663 : N-Queen  (0) 2019.03.07
[SWEA] 7236 : 저수지의 물의 총 깊이 구하기  (1) 2019.03.07
[SWEA] 1861 : 정사각형 방  (0) 2019.03.07

+ Recent posts

티스토리툴바