문제 >> [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

문제 >> [BOJ] 9663 : N-Queen


Backtracking을 이용하는 대표적인 문제입니다 -!

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
//BOJ :: 9663 N-Queen
//2019-03-05
public class Main9663_NQueen {
    static int[][] map;
    static int n, ans;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(bf.readLine());
        ans = 0;
 
        // 1행에서 퀸의 위치를 정해준다.
        for (int j = 0; j < n; j++) {
            map = new int[n][n];
            solve(0, j, 1);
        }
        System.out.println(ans);
    }
 
    static int[] dx = { -1, 0, 1, 0, 1, -1, 1, -1 };
    static int[] dy = { 0, 1, 0, -1, -1, -1, 1, 1 };
 
    public static void solve(int y, int x, int q) {
 
        map[y][x]++; // visited
        
        //(y,x) 좌표에 퀸을 놓고 다른 퀸을 놓을수 없는 곳에 visit check 를 한다.
        //퀸의 위치를 중심으로 8방향에 대하여 배열의  범위를 초과하는 지점까지 while문을 반복한다.
        for (int i = 0; i < 8; i++) {
            int ny = y, nx = x;
            while (true) {
                ny += dy[i];
                nx += dx[i];
 
                if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1)
                    break;
                map[ny][nx]++;
            }
        }
 
        if (q == n) {// 종료조건 : n개의 퀸을 놓으면 재귀함수를 종료한다.
            ans++;
            return;
        }
        
        //다음행인 (y+1)행에 퀸을 놓을 수 있는 곳을 탐색한다.
        for (int k = 0; k < n; k++) {
            if (map[y + 1][k] > 0)
                continue; // 방문한 곳은 continue;
 
            solve(y + 1, k, q + 1);
            
            
            //Backtracking
            //놓았던 퀸을 회수하고,
            map[y + 1][k]--;
            //해당 퀸에 의해 visit 체크 되었던 곳을 해제한다.
            for (int i = 0; i < 8; i++) {
                int ny = y + 1, nx = k;
                while (true) {
                    ny += dy[i];
                    nx += dx[i];
 
                    if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1)
                        break;
                    map[ny][nx]--;
                }
            }
 
        }
 
    }
}
 
cs


**** visit 체크를 boolean 타입이 아닌 cnt++ 로 해주는 이유


여러 퀸을 놓으면서 해당 퀸에 의해서 8방향으로 visit 체크 되는곳이 겹치는 경우가 발생합니다.


만약, 재귀 함수가 끝나고 퀸을 회수하면서 visit 체크를 해제할때 boolean 타입으로 true를 false로 바꿔준다면


다른 퀸에 대해 visit 체크 되었던 곳임에도 불구하고 visit이 해제 될 수 있습니다.


int 형으로 카운트 해주며 visit을 체크하면 그런 상황을 방지할 수 있읍니당 ,,

저작자표시

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

[SWEA] 5656 : [모의 SW 역량테스트] 벽돌 깨기  (1) 2019.03.07
[SWEA] 1258 : [S/W 문제해결 응용] 7일차 - 행렬찾기  (0) 2019.03.07
[SWEA] 7236 : 저수지의 물의 총 깊이 구하기  (1) 2019.03.07
[SWEA] 1861 : 정사각형 방  (0) 2019.03.07
[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07

문제 >> [SWEA] 7236 : 저수지의 물의 총 깊이 구하기

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.StringTokenizer;
 
//SWEA :: 7236 저수지의 물의 총 깊이 구하기
//2019-03-07
public class Solution_7236_저수지의물의총깊이구하기_유승아 {
    static char[][] map;
    static int[][] count;
    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 char[n][n];
            count = 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] = st.nextToken().charAt(0);
                }
            } // input
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j] == 'G')
                        continue;
                    solve(i, j);
                    ans = ans < count[i][j] ? count[i][j] : ans;
                }
            }
            System.out.println("#" + tc + " " + ans);
 
        } // end of tc
    }// end of main
 
    static int[] dx = { -1, 1, 0, 0, 1, 1, -1, -1 };
    static int[] dy = { 0, 0, -1, 1, -1, 1, -1, 1 };
 
    public static void solve(int y, int x) {
 
        int wCnt = 0;
        for (int i = 0; i < 8; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
 
            if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1)
                continue;
 
            if (map[ny][nx] == 'W')
                wCnt++;
 
        }
 
        if (wCnt == 0)
            count[y][x] = 1;
        else
            count[y][x] = wCnt;
 
    }
 
}
 
cs


저작자표시

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

[SWEA] 1258 : [S/W 문제해결 응용] 7일차 - 행렬찾기  (0) 2019.03.07
[BOJ] 9663 : N-Queen  (0) 2019.03.07
[SWEA] 1861 : 정사각형 방  (0) 2019.03.07
[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07
[BOJ] 1012 : 유기농배추  (1) 2019.02.17
문제 >> [SWEA] 1861 : 정사각형 방


dp로 풀었음.

완탐도 가능 !



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.InputStreamReader;
import java.util.StringTokenizer;
 
//SWEA :: 1861 정사각형 방
//2019-03-07
public class Solution1861_정사각형방_유승아 {
    static int[][] box;
    static int[][] dp;
    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());
            box = new int[n][n];
            dp = new int[n][n]; //방문한 방의 갯수를 저장할 배열
 
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
                for (int j = 0; j < n; j++) {
                    box[i][j] = Integer.parseInt(st.nextToken());
                }
            } // input
 
            int max = Integer.MIN_VALUE;
            int start = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //dp배열의 값이 0일 때만 방문
                    //0이 아닌 경우는 이미 해당 방에서 갈 수 있는 최대값이 저장되어 있다.
                    if (dp[i][j] == 0) {
                        solve(i, j);
                    }
                    
                    //최대값 갱신
                    if (max < dp[i][j]) {
                        max = dp[i][j];
                        start = box[i][j];
                    } else if (max == dp[i][j]) {
                        //최대값이 같은 경우에는 start 숫자가 작은 값을 저장한다.
                        start = start > box[i][j] ? box[i][j] : start;
                    }
 
                }
            }
 
            System.out.println("#" + tc + " " + start + " " + max);
        } // end of tc
 
    }// end of main
 
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
 
    public static void solve(int y, int x) {
        dp[y][x] = 1;
 
        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 )
                continue;
 
            if (box[ny][nx] == box[y][x] + 1) {
                //아직 방문한 적이 없을때만 solve 함수를 호출한다.
                if( dp[ny][nx] == 0) solve(ny, nx);
                
                //최대값으로 갱신한다.
                if (dp[y][x] < 1 + dp[ny][nx]) {
                    dp[y][x] = 1 + dp[ny][nx];
                }
            }
        }
    } // end of solve
 
}
 
cs


저작자표시

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

[BOJ] 9663 : N-Queen  (0) 2019.03.07
[SWEA] 7236 : 저수지의 물의 총 깊이 구하기  (1) 2019.03.07
[BOJ] 8983 : 사냥꾼 / [JUNGOL] 2364 : 사냥꾼  (1) 2019.03.07
[BOJ] 1012 : 유기농배추  (1) 2019.02.17
[BOJ] 1931 : 회의실배정 (++그리디 알고리즘에 대한 고찰)  (2) 2019.02.17

+ Recent posts

티스토리툴바