문제 링크 : https://www.acmicpc.net/problem/1799


처음에 문제를 풀고 제출을 했을 때 시간 초과가 났다.

나름 잘 푼것 같은데 시간초과가 나서 왜인지 고민하다가 다른사람들의 답을 보았는데

체스판 흑영역과 백영역을 구분해서 탐색하는 방법으로 시간을 줄여야 했던거였다.

아마 혼자서 그 방법을 생각하려면 굉장히 많은 시간이 들었을것같다.


그런데 흑백으로 구분해서 풀고나니 틀렸습니다가 떴다.

아무리 생각해도 로직이 잘못된것 없는것같아서 맞왜틀맞왜틀 하고있었는데 배열사이즈를 넉넉하게 잡아주었더니 맞았다.



문제 접근


1. 비숍은 이동방향이 대각선이므로 하나의 대각선에는 하나의 비숍만이 위치해야한다.


2. 오른쪽 위로 향하는 대각선을 기준으로 잡고 0부터 2n-2까지의 대각선(0부터 시각하였으므로 총 2n-1개의 대각선)을 재귀함수를 통해 완전탐색을 하며 하나의 대각선 마다 비숍의 자리를 골라주었다.

 비숍을 선택하지 않고 대각선을 넘기는 경우도 고려 해주었다.

 오른쪽 아래로 향하는 대각선과의 중복을 확인해주기 위해 비숍을 놓을 때 decr배열에 표시를 해주었고, 비숍을 놓기전에 decr배열을 보고 놓을수 있는지 없는지를 판단하였다.


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
#include <iostream>
#include <algorithm>
using namespace std;
 
int n, maxR = 0;
int map[20][20];
bool decr[30];
 
void recur(int line, int picknum) {
    if (line >= 2 * n - 1) {
        maxR = max(maxR, picknum);
        return;
    }
 
    for (int y = 0; y <= line; y++) {
        int x = line - y;
        if (map[y][x] == 0 || decr[y - x + n - 1] == true) continue;
 
        decr[y - x + n - 1] = true;
        recur(line + 2, picknum + 1);
        decr[y - x + n - 1] = false;
    }
    recur(line + 2, picknum);
}
 
int main()
{
    int answer = 0;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    recur(0, 0);
    answer += maxR;
 
    maxR = 0;
    recur(1, 0);
    answer += maxR;
 
    cout << answer << endl;
}
cs






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

백준 10974 모든 순열  (0) 2019.02.25
백준 1764 듣보잡  (0) 2019.02.20
백준 9663번 N-Queen  (0) 2019.01.28
백준 1325번 효율적인 해킹  (0) 2019.01.23
백준 2468번 안전영역  (0) 2019.01.22


문제 링크 : https://www.acmicpc.net/problem/9663;


처음에 별생각없이 무식하게 2중for문 돌려서 구현했더니 답이 나오긴 나오는데 입력값이 10이 넘어가니까 시간이 너무 오래 걸렸다.

아니나 다를까 시간초과에 걸리고 결국 다른사람의 풀이를 보고 풀었다..

이 문제를 풀면서 문제 구상에 더 많은 시간을 써야 한다는것을 느꼈다.

직관적인 풀이법 보다 더 문제를 단순화하고 로직을 최소화하는 방법을 생각하는데 많은 시간을 들여야겠다고 생각했다.


아무튼 결국 풀이에 대한 접근은


1. N x N 칸에 N개의 퀸을 서로 공격할수 없게 놓아야 하므로 하나의 행에 하나의 퀸만 놓아야 한다


2. 퀸이 움직일수 있는 위치는 가로세로 대각선이다.


3. 행을 기준으로 퀸을 놓기때문에 내가 놓을 행에 퀸이 중복되는 경우는 없다.

퀸이 놓기 전엔 열과 대각선상에 퀸이 중복되는지만 확인해주면된다.


4. 열과 대각선상의 중복은 각각 배열 col, inc, decr에 저장하며 확인한다.

대각선상의 중복여부는 양의 기울기를 갖는 대각선의 x, y 좌표의 합이 일정하다는 사실과, 음의 기울기를 갖는 대각선의 x, y좌표의 차가 일정하다는 사실을 이용하였다.





코드는 아래와 같다


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
#include <iostream>
using namespace std;
 
int n, ans = 0;
bool col[14];
bool inc[27];
bool decr[27];
 
void recur(int r) {
    if (r >= n) {
        ans++;
        return;
    }
 
    for (int i = 0; i < n; i++) {
        if (col[i] || inc[r + i] || decr[n - (r - i) - 1]) continue;
        
        col[i] = inc[r + i] = decr[n - (r - i) - 1] = true;
        recur(r + 1);
        col[i] = inc[r + i] = decr[n - (r - i) - 1] = false;
 
    }
}
 
int main()
{
    cin >> n;
    recur(0);
    cout << ans << endl;
}
cs










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

백준 1764 듣보잡  (0) 2019.02.20
백준 1779번 비숍  (0) 2019.01.29
백준 1325번 효율적인 해킹  (0) 2019.01.23
백준 2468번 안전영역  (0) 2019.01.22
백준 1012번 유기농 배추  (0) 2019.01.21


문제 링크 : https://www.acmicpc.net/problem/1325


입력값 수의 범위가 너무 크길래 2차원 인접행렬로 구혔했다가는 메모리가 너무 많이필요할것같아서

2차원 벡터를 사용하여 인접해있는 정보를 추가해주어야 겠다고 생각했다.

그러나 c++로 알고리즘을 푼지 얼마 안된나는 2차원 벡터는 커녕 1차원 벡터도 낯설었기 때문에 2차원 벡터를 구글링하였다.

하지만 검색결과가 탐탁지 않아서 1325번 효율적인 해킹문제를 푼사람의 코드를 보고 2차원 벡터 구현을 참고하려고 검색을 하였는데

2차원벡터 선언과 사용을 보다가 그만 소스를 너무 많이 봐버렸다.

물론 대략적인 구상은 한 채로 소스를  보긴 했지만 구체척으로 구상하지 않은 상태에서 완성된 소스를 봐버려서

vitit배열 사용과 해킹할수있는 컴퓨터수의 최대값을 저장하여 마지막에 그값과 같은 값을 가지는 컴퓨터의 번호를 출력하는것 등 의도치않게 그 블로그에 있던 코드를 좀 많이 참고하게 되었다..


일단 푼 방법은

1. 입력값을 2차원 배열에 저장한다.

2. 배열을 순회하며 각 컴퓨터를 기준으로 dfs를 실행하며 해킹할수있는 컴퓨터의 수를 구하고 그 값을 hacking배열에 저장하고 그 중 최대값을 max_count에 유지한다.

3. hacking배열을 순회하며 max_count와 같은 값을 가지는 컴퓨터의 번호를 출력한다.


이렇게 풀었다.


c++로 풀었음에도 불구하고 시간이 3644ms나 걸렸다. 효율적으로 풀지 못한것같다.

물론 문제의 제한시간은 5초긴 했지만 그래도 맞은사람들 보면 세자리ms인 사람도있고 천이나 이천대도 많은걸보면 삼천대는 좀 아쉬운것같다.



아무튼 아래는 소스코드이다.



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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
 
vector<int> graph[10001];
bool visit[10001] = { false };
int hacking[10001] = { 0 };
int max_count = 0 ;
 
void dfs(int current, int start) {
    visit[current] = true;
 
    for (int i = 0; i < graph[current].size(); i++) {
        int next = graph[current][i];
        if (visit[next] == true) continue;
 
        dfs(next, start);
        hacking[start] += 1;
    }
}
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t2 >> t1;
        graph[t1].push_back(t2);
    }
 
    for (int i = 0; i <= n; i++) {
        if (graph[i].size() == 0) continue;
 
        memset(visit, false, sizeof(bool)*(n+1));
        dfs(i, i);
        max_count = max(max_count, hacking[i]);
    }
 
    for (int i = 0; i <= n; i++) {
        if (hacking[i] == max_count) {
            cout << i << " ";
        }
    }
}
cs



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

백준 1779번 비숍  (0) 2019.01.29
백준 9663번 N-Queen  (0) 2019.01.28
백준 2468번 안전영역  (0) 2019.01.22
백준 1012번 유기농 배추  (0) 2019.01.21
백준 1966번 프린터 큐  (0) 2019.01.21


문제 링크 : https://www.acmicpc.net/problem/2468



1. 입력을 받으며 높이의 최대값을 max_height에 저장하였다.


2. 0부터 max_height까지 반복하며

map배열을 훑으며 max_height보다 높이가 높고 방문하지 않은 지점이 있다면 그 좌표값을 넣어 dfs를 실행하였다.

dfs를 실행할때마다 count의 값을 올려주어 영역의 갯수를 구하였다.

반복이 한번 끝날때마다 영역의 갯수중 큰값을 max_count에 갱신해주었다.


3. max_count를 출력하였다.



아래는 소스코드이다.



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
#include <iostream>
#include <algorithm>
#include <string.h>
#define MAX 100
 
using namespace std;
 
int n;
int map[MAX][MAX];
bool visit[MAX][MAX];
int dy[] = { 0, 0, -1, 1 };
int dx[] = { -1, 1, 0, 0 };
 
void dfs(int y, int x, int rain) {
    visit[y][x] = true;
 
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
 
        if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
        if (map[ny][nx] <= rain || visit[ny][nx]) continue;
 
        dfs(ny, nx, rain);
    }
}
 
int main()
{
    int max_height=0, count, max_count=0;
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int t;
            cin >> t;
            map[i][j] = t;
            max_height = max(max_height, t);
        }
    }
 
    for (int k = 0; k < max_height; k++) {
        count = 0;
        memset(visit, false, sizeof(visit));
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] > k && visit[i][j] == false) {
                    dfs(i, j, k);
                    count++;
                }
            }
        }
        max_count = max(max_count, count);
    }
 
    cout << max_count;
}
cs



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

백준 9663번 N-Queen  (0) 2019.01.28
백준 1325번 효율적인 해킹  (0) 2019.01.23
백준 1012번 유기농 배추  (0) 2019.01.21
백준 1966번 프린터 큐  (0) 2019.01.21
백준 15686번 치킨 배달  (0) 2019.01.17


문제 링크 : https://www.acmicpc.net/problem/1012


배추가 있는 영역의 갯수를 세는 문제이다.


1. 배추가 있는 곳의 좌표를 입력받아 int형 2차원배열 map에 표시해주었다


2. map의 좌표를 순서대로 탐색하며 값이 1이고 방문하지 않은 좌표를 발견하면 bfs로 탐색을 하였고 bfs를 실행하는 횟수를 세서 출력하였다.



c++로 풀어서 제출하니 실행시간이 0ms로 나와서 놀랐다. 자바보다 빠르다는 건 알고있었지만 이정로도 차이가 많이 날줄은 몰랐다.

c++ 연습을 하려고 c++로 짰는데 문법이 익숙하지않아서 버벅댔다. 그래서 코드가 이쁘지 않을수도 있다.

풀고나서 다른사람들의 소스코드를 보니 visit배열을 사용하지않고 그냥 map배열의 1값을 0으로 지우는 방법으로 짠 사람도 있었고,

map의 좌표를 다 탐색하지않고 배추정보 입력시 좌표값을 vector에 넣어 뒀다가  그 좌표만을 탐색하는 방법으로 짠 사람도 있었다.

두 방법다 효율을 높일수있는 방법이지만 난 아직 c++문법이 익숙치 않아서 그냥 기본적인 방법으로 푼것으로 만족하였다.

다음에 비슷한 경우를 만나면 저런 방법을 사용해봐야겠다.



아래는 소스코드이다.


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
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
 
int m, n;
int map[50][50];
bool visit[50][50];
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { -1, 1, 0, 0 };
 
void bfs(int y, int x) {
    visit[y][x] = true;
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
 
    while (!q.empty()) {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if (map[ny][nx] == 1 && visit[ny][nx] == false) {
                visit[ny][nx] = true;
                q.push(make_pair(ny, nx));
            }
        }
    }
}
 
int main()
{
    int t, k, count;
    cin >> t;
 
    for (int i = 0; i < t; i++) {
        cin >> m >> n >> k;
        count = 0;
        for (int j = 0; j < n; j++) {
            memset(map[j], 0, sizeof(int) * 50);
            memset(visit[j], false, sizeof(int) * 50);
        }
 
        for (int j = 0; j < k; j++) {
            int x, y;
            cin >> x >> y;
            map[y][x] = 1;
        }
 
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < m; b++) {
                if (map[a][b] == 1 && visit[a][b] == false) {
                    bfs(a, b);
                    count++;
                }
            }
        }
 
        cout << count << endl;
    }
}
cs



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

백준 1325번 효율적인 해킹  (0) 2019.01.23
백준 2468번 안전영역  (0) 2019.01.22
백준 1966번 프린터 큐  (0) 2019.01.21
백준 15686번 치킨 배달  (0) 2019.01.17
백준 14502번 연구소  (0) 2019.01.16


문제 링크 : https://www.acmicpc.net/problem/1966


그냥 문제에서 하라는 대로 그대로 구현하였다.


1. 우선 '중요도'와 '초기 인덱스' 값을 갖는 Doc클래스를 하나 만들었다.


2. ArrayList를 만들고 그안에 입력값을 Doc객체를 만들어 넣어주었다.


3. ArrayList의 가장 앞에 있는 원소의 '중요도'를 확인하고

 뒤의 원소중 가장 앞에있는 원소보다 중요도가 높은 원소가 하나라도 있다면, 맨앞의 원소를 뒤로 보냈다.

 만약 그렇지 않다면 맨앞의 원소가 찾는 원소인지 확인하여 찾는 원소가 아니라면 삭제하였고, 찾는 원소라면 몇번째 원소인지 출력하고 삭제한 후 반복을 종료했다.


아래는 소스코드이다.


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
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        
        int t, n, m, count;
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        
        for(int i=0; i<t; i++) {
            n = sc.nextInt();
            m = sc.nextInt(); //찾을 인덱스
            count = 0;
            ArrayList<Doc> ar = new ArrayList<Doc>();
            
            for(int j=0; j<n; j++) {
                int imp = sc.nextInt();
                ar.add(new Doc(imp, j));
            }
            
            while(!ar.isEmpty()) {
                boolean find = false;
                for(int k=1; k<ar.size(); k++) {
                    if(ar.get(k).importance> ar.get(0).importance) {
                        find = true;
                        break;
                    }
                }
                
                Doc first = ar.get(0);
                if(find) {
                    ar.add(first);
                    ar.remove(0);
                }
                else {
                    count++;
                    if(first.index==m) {
                        System.out.println(count);
                        break;
                    }
                    else {
                        ar.remove(0);
                    }
                }
            }
        }
    }
}
 
class Doc {
    int importance;
    int index;
    
    Doc(int importance, int index) {
        this.importance = importance;
        this.index = index;
    }
}
cs



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

백준 2468번 안전영역  (0) 2019.01.22
백준 1012번 유기농 배추  (0) 2019.01.21
백준 15686번 치킨 배달  (0) 2019.01.17
백준 14502번 연구소  (0) 2019.01.16
백준 6603번 로또  (0) 2019.01.14

 문제 링크 : https://www.acmicpc.net/problem/15686


입력으로는

집은 1, 치킨집은 2, 빈공간은 0으로 나태고있는 n사이즈의 맵과

골라야학 치킨집의 갯수 m이 주어진다.


맵에 존재하는 치킨집중 m개를 선택하였을때 도시의 치킨거리의 최솟값을 출력하는 문제이다.

(자세한 설명은 분제링크를 참조하세요)


아무튼 그래서 나는 우선 입력받으며 집의 목록과 치킨집의 목록을 각각 ArrayList에 저장하였다.


치킨집의 전체 갯수에서 m개를 선택하는 모든경우를 구하였고.


각각의 경우마다 치킨거리를 구해주었고 그중 최소값을 찾아 출력하였다.



아래는 소스코드이다.

기저 사례에 해당하는 내용이 길어지니까 가독성이 떨어지는것같다. 다음부터는 함수로 따로 빼야겠다.


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
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    static int m, minSum;
    static ArrayList<Point> house = new ArrayList<Point>();
    static ArrayList<Point> beer = new ArrayList<Point>();
    static ArrayList<Integer> selected = new ArrayList<Integer>();
    
    public static void main(String[] args) {
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                int p = sc.nextInt();
                if(p==1) house.add(new Point(i, j));
                else if(p==2) beer.add(new Point(i, j));
            }
        }
        
        minSum = Integer.MAX_VALUE;
        pick(m);
        System.out.println(minSum);
    }
    
    
    public static void pick(int toPick) {
        if(toPick == 0) {
            int sum = 0;
            
            for(int i=0; i<house.size(); i++) {
                int minHouseToBeer = Integer.MAX_VALUE;
                
                for(int j=0; j<selected.size(); j++) {
                    Point houseP = house.get(i);
                    Point beerP = beer.get(selected.get(j));
                    int distance = calc(houseP, beerP);
                    minHouseToBeer = Math.min(minHouseToBeer, distance);
                }
                
                sum += minHouseToBeer;
            }
            
            minSum = Math.min(minSum, sum);
            return;
        }
        
        int small = selected.isEmpty() ? 0 : selected.get(selected.size()-1) + 1;
        // 0 부터
        for(int i=small; i<beer.size(); i++) {
            selected.add(i);
            pick(toPick - 1);
            selected.remove(selected.size()-1);
        }
    }
    
    public static int calc(Point a, Point b) {
        int r1 = a.y - b.y;
        if(r1<0) r1 *= -1;
        
        int r2 = a.x - b.x;
        if(r2<0) r2 *= -1;
        
        return r1 + r2;
    }
    
}
 
class Point {
    int y, x;
    
    Point(int y, int x) {
        this.y = y;
        this.x = x;
    }
    
    public String toString() {
        String s = "("+y+", "+x+")";
        return s;
    }
}
cs



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

백준 1012번 유기농 배추  (0) 2019.01.21
백준 1966번 프린터 큐  (0) 2019.01.21
백준 14502번 연구소  (0) 2019.01.16
백준 6603번 로또  (0) 2019.01.14
백준 1987번 알파벳  (0) 2019.01.05


문제 링크 : https://www.acmicpc.net/problem/14502


브루트포스 문제이다. (참고로 삼성 기출 문제이다.)

완전탐색으로 벽을 세우고 그래프를 탐색하며 바이러스를 퍼트린 후 안전영역의 크기를 구하는 방식으로 풀 수 있다.


처음에 코드를 짠 후에 실행을 해보는데 이클립스에서 돌아가는데도 너무 오래 걸리길래

뭐가 문제일까 생각 하다가 반목문을 2개 줄일 방법을 생각했다.

근데 아무리 생각해봐도 반복 두개 더 줄인다고 나아질 속도가 아니라서 코드를 다시보니 바보같이 재귀호출하며 벽을 3개 세운후에 return을 하지 않고 있었다.

리턴문만 추가 하고 돌려보니 바로 돌아가길래 제출해보니 맞았습니다를 받았다.


맞았기때문에 반복문 2개는 그냥 줄이지 않기로 했다...


그래프를 탐색할땐 bfs를 사용하였다. 완전탐색을 하며 이미 재귀호출을 하고있는데 그 안에서 또 dfs를 사용하여 재귀호츨을 하면 혹시 메모리가 부족할까 싶어서 큐를 사용하는 bfs를 이용하였다.


아래는 소스코드이다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    static int n, m, maxCount;
    static int[][] map;
    static int[][] tmp;
    static boolean[][] visited;
    static int[] dy = { 0, 0, -1, 1 };
    static int[] dx = { -1, 1, 0, 0 };
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        tmp = new int[n][m];
        maxCount = 0;
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                map[i][j] = sc.nextInt();
            }
        }    
        
        select(0, -1, 3);
        System.out.println(maxCount);
    }
    
    
    public static void select(int y, int x, int toPick) {
        if(toPick==0) {
            visited = new boolean[n][m];
            bfs();
            int count = 0;
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if(tmp[i][j]==0) count++;
                }
            }
            maxCount = Math.max(count, maxCount);
            return;
        }
        
        if(x+1<m) x+=1;
        else {
            if(y+1<n) {
                y+=1;
                x=0;
            } else return;
        }
        
        for(int i=y; i<n; i++) {
            for(int j=x; j<m; j++) {
                if(map[i][j]==1 || map[i][j]==2) continue;
                map[i][j] = 1;
                select(i, j, toPick-1);
                map[i][j] = 0;
            }
            x = 0;
        }
    }
    
    public static void bfs() {
        for(int i=0; i<map.length; i++) {
            System.arraycopy(map[i], 0, tmp[i], 0, map[i].length);
        }
        Queue<Point> q = new LinkedList<Point>();
 
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(tmp[i][j]==2 && visited[i][j]==false) {
                    visited[i][j] = true;
                    q.offer(new Point(i, j));
                    
                    while(!q.isEmpty()) {
                        Point current = q.poll();
                        for(int k=0; k<4; k++) {
                            int ny = current.y + dy[k];
                            int nx = current.x + dx[k];
                            if(ny<0 || nx<0 || ny>=n || nx>=m) continue;
                            if(tmp[ny][nx]==1 || visited[ny][nx]==true) continue;
                            
                            visited[ny][nx] = true;
                            tmp[ny][nx] = 2;
                            q.offer(new Point(ny, nx));
                        }
                    }
                }
            }
        }
    }
}
 
class Point {
    int y, x;
    
    Point(int y, int x) {
        this.y = y;
        this.x = x;
    }
}
cs



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

백준 1966번 프린터 큐  (0) 2019.01.21
백준 15686번 치킨 배달  (0) 2019.01.17
백준 6603번 로또  (0) 2019.01.14
백준 1987번 알파벳  (0) 2019.01.05
백준 11403번 경로 찾기  (0) 2019.01.04

+ Recent posts

티스토리툴바