www.acmicpc.net/problem/20304

 

20304번: 비밀번호 제작

서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부

www.acmicpc.net

bfs에 비트마스킹까지 해야하는 문제입니다.

 

관리자 계정 비밀번호와 해커가 로그인 시도에 사용된 비밀번호의 안전거리로 계산한 안전도를 최대로 해야합니다.

우선 로그인 시도에 사용된 비밀번호가 관리자 계정 비밀번호와 같으면 안전거리는 0입니다. (고정)

이를 큐에 넣고 비트마스킹을 이용하여 bfs로 탐색을 합니다. 큐에는 번호와 안전도를 유지합니다.

 

이제 1부터 왼쪽시프트를 하면서 x와 &연산을 합니다. (y = x & i)

y > 0이면 같은 자릿수가 있다는 의미이며, x - i를 한 값이 거리가 1인 숫자입니다.

그리고 y == 0이면 같은 자릿수가 없다는 의미이며, x + i를 한 값이 거리가 1인 숫자입니다.

 

이 과정을 반복하여 cnt의 max를 구하여 출력합니다.

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Queue<int[]> q = new LinkedList<>();
    static int visit[];
    static int N, M, ans;
 
    static void bfs() {
        while (!q.isEmpty()) {
            int x = q.peek()[0];
            int cnt = q.poll()[1];
 
            ans = Math.max(ans, cnt);
            for (int i = 1; i <= N; i = i << 1) {
                int y = x & i;
 
                if (y > 0) {
                    if (visit[x - i] != -1)
                        continue;
                    q.add(new int[] { x - i, cnt + 1 });
                    visit[x - i] = cnt + 1;
                } else {
                    if (x + i > N || visit[x + i] != -1)
                        continue;
                    q.add(new int[] { x + i, cnt + 1 });
                    visit[x + i] = cnt + 1;
                }
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        visit = new int[N + 1];
        Arrays.fill(visit, -1);
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            x = Integer.parseInt(st.nextToken());
            q.add(new int[] { x, 0 });
            visit[x] = 0;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 2206 벽 부수고 이동하기  (0) 2021.02.13
boj 14502 연구소  (0) 2021.02.12
boj 2606 바이러스  (0) 2021.02.03
boj 1012 유기농 배추  (0) 2021.02.03
boj 16956 늑대와 양  (0) 2021.02.03

www.acmicpc.net/problem/2606

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어

www.acmicpc.net

처음에 1번 컴퓨터가 바이러스에 걸리고 이 컴퓨터로 인해 바이러스에 걸리는 컴퓨터가 몇 대인지 출력하는 문제입니다.

 

이 문제는 간단한 bfs로 해결할 수 있습니다.

입력으로 u와 v가 주어지면 둘이 연결되어있다는 말입니다.

이 그래프는 양방향 그래프이기 때문에 u의 간선에도 v를 추가하고, v의 간선에도 u를 추가해야합니다.

 

그 다음 1번부터 시작하여 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
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 Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer> list[];
    static boolean visit[];
    static int N, M, ans;
 
    static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        visit[1] = true;
        while (!q.isEmpty()) {
            int v = q.peek();
 
            q.remove();
 
            for (int i = 0; i < list[v].size(); i++) {
                int next = list[v].get(i);
 
                if (visit[next])
                    continue;
 
                q.add(next);
                visit[next] = true;
                ans++;
            }
        }
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new ArrayList[N + 1];
        visit = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
 
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            list[u].add(v);
            list[v].add(u);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
        System.out.println(ans);
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 14502 연구소  (0) 2021.02.12
boj 20304 비밀번호 제작  (0) 2021.02.08
boj 1012 유기농 배추  (0) 2021.02.03
boj 16956 늑대와 양  (0) 2021.02.03
boj 20419 화살표 미로 (Easy)  (0) 2021.01.23

www.acmicpc.net/problem/1012

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 

www.acmicpc.net

배추영역 하나에 지렁이 한마리가 들어가고 최종적으로 배추밭에 필요한 지렁이의 수를 구하는 문제이며

탐색을 통해 배추영역의 갯수를 구하는 문제입니다.

 

저는 bfs를 사용했습니다.

입력으로 배추의 위치가 X, Y로 주어지면 list[X][Y] = 1로 표시합니다.

모든 입력을 다 받고 2중 for문을 돌려서 해당 칸이 1이면서 아직 방문하지 않은 위치면 그 위치를 시작으로 bfs를 돌립니다.

 

bfs로 현재 위치에서 주변에 1이 있는 좌표들을 큐에 넣고 중복체크를 해줍니다.

bfs 탐색이 종료되면 한 구역 탐색이 끝난 것이므로 ans를 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static boolean visit[][];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int list[][];
    static int N, M, K, ans;
 
    static void print() {
        sb.append(ans + "\n");
        ans = 0;
    }
 
    static void bfs(int sx, int sy) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { sx, sy });
        visit[sx][sy] = true;
        while (!q.isEmpty()) {
            int x = q.peek()[0];
            int y = q.peek()[1];
 
            q.remove();
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (visit[nx][ny] || list[nx][ny] == 0)
                    continue;
 
                q.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
    }
 
    static void func() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (list[i][j] == 1) {
                    if (visit[i][j])
                        continue;
 
                    bfs(i, j);
                    ans++;
                }
            }
        }
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        list = new int[N][M];
        visit = new boolean[N][M];
 
        while (K-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            list[u][v] = 1;
        }
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
            func();
            print();
        }
        
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 20304 비밀번호 제작  (0) 2021.02.08
boj 2606 바이러스  (0) 2021.02.03
boj 16956 늑대와 양  (0) 2021.02.03
boj 20419 화살표 미로 (Easy)  (0) 2021.01.23
boj 2638 치즈  (0) 2021.01.22

www.acmicpc.net/problem/16956

 

16956번: 늑대와 양

크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게

www.acmicpc.net

 

문제 분류는 bfs로 되어있지만 bfs를 사용하지 않아도 해결 가능한 문제입니다.

저는 bfs방식으로 양의 위치를 큐에 담아서 하나씩 꺼내 확인하는 방법과

2중 for문을 이용해서 양의 위치에서 확인하는 방법으로 2가지로 해결해 보았습니다.

 

두 방법 모두 양의 위치에서 상, 하, 좌, 우 방향에 늑대가 있는지 확인합니다.

늑대가 있으면 0출력후 리턴, 없으면 놓을 수 있는 모든 방향에 울타리를 설치합니다.

 

문제가 스페셜저지이기 때문에 예제와 답이 다르게 나와도 늑대가 양이 있는 칸으로 갈수없다면 정답으로 할 수 있습니다. (물론 첫째줄에 출력하는 0과 1은 맞아야합니다.)

 

[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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Queue<int[]> q = new LinkedList<>();
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static boolean chk;
    static char list[][];
    static int N, M;
 
    static void print() {
        if (chk) {
            System.out.println(0);
            return;
        }
 
        StringBuffer sb = new StringBuffer();
        sb.append("1\n");
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sb.append(list[i][j]);
            }
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
 
    static void func() {
        while (!q.isEmpty()) {
            int x = q.peek()[0];
            int y = q.peek()[1];
            q.remove();
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (list[nx][ny] == 'S' || list[nx][ny] == 'D')
                    continue;
                if (list[nx][ny] == 'W') {
                    chk = true;
                    break;
                }
 
                list[nx][ny] = 'D';
            }
 
            if (chk)
                break;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new char[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            for (int j = 0; j < M; j++) {
                if (list[i][j] == 'S') {
                    q.add(new int[] { i, j });
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}
 cs

 

[2중 for문을 통한 탐색]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static char list[][];
    static int N, M;
    static boolean chk;
 
    static void print() {
        if (chk) {
            System.out.println(0);
            return;
        }
 
        StringBuffer sb = new StringBuffer();
        sb.append("1\n");
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sb.append(list[i][j]);
            }
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
 
    static void func() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (list[i][j] == 'S') {
                    for (int k = 0; k < 4; k++) {
                        int nx = i + direct[k][0];
                        int ny = j + direct[k][1];
 
                        if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                            continue;
                        if (list[nx][ny] == 'S' || list[nx][ny] == 'D')
                            continue;
                        if (list[nx][ny] == 'W') {
                            chk = true;
                            return;
                        }
 
                        list[nx][ny] = 'D';
                    }
                }
            }
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new char[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 2606 바이러스  (0) 2021.02.03
boj 1012 유기농 배추  (0) 2021.02.03
boj 20419 화살표 미로 (Easy)  (0) 2021.01.23
boj 2638 치즈  (0) 2021.01.22
boj 17142 연구소 3  (0) 2021.01.22

www.acmicpc.net/problem/20419

 

20419번: 화살표 미로 (Easy)

첫번째 줄에는 미로의 행 R, 열 C, 준서가 가진 주문서 세트의 개수 K가 주어진다. 두번째 줄부터 R줄에 걸쳐 화살표 미로의 지도가 입력된다. 각 줄마다 "UDLR"로만 이루어진 길이 C의 문자열이 입

www.acmicpc.net

문제를 잘못 이해하는 바람에 4번이나 WA를 받고 깨달았습니다...

 

이 문제는 (1, 1)에서 (R, C)로 이동하면 탈출하는 문제입니다.

저는 (R, C)에서 오른쪽으로 가느니 밑으로 가느니 이런 삽질을 하였습니다 ㅠㅠ

 

아무튼..

 

문제는 bfs로 해결하였습니다.

K가 0아니면 1이었기 때문에 queue에 {x좌표, y좌표, 주문서 사용}를 저장하였고,

 

해당 칸에 명시되어 있는 방향으로 이동한 좌표, 주문서를 사용하며 이동한 좌표 모두 queue에 담으며 탐색하였습니다.

 

 

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
package BOJ.bfs;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Boj20419 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int direct[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    static boolean visit[][][];
    static int N, M, K;
 
    static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { 0, 0, 0 });
        visit[0][0][0] = true;
        while (!q.isEmpty()) {
            int x = q.peek()[0];
            int y = q.peek()[1];
            int k = q.peek()[2];
            q.remove();
 
            if (x == N - 1 && y == M - 1) {
                System.out.println("Yes");
                return;
            }
 
            int d = list[x][y];
            int nx = x + direct[d][0];
            int ny = y + direct[d][1];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                if (!visit[nx][ny][k]) {
                    q.add(new int[] { nx, ny, k });
                    visit[nx][ny][k] = true;
                }
            }
 
            if (K > 0) {
                if ((1 & k) == 0) { // Left
                    int nk = k | 1;
                    int nd = d - 1;
                    if (nd == -1)
                        nd = 3;
 
                    nx = x + direct[nd][0];
                    ny = y + direct[nd][1];
                    if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                        if (!visit[nx][ny][nk]) {
                            q.add(new int[] { nx, ny, nk });
                            visit[nx][ny][nk] = true;
                        }
                    }
                }
 
                if ((2 & k) == 0) { // Right
                    int nk = k | 2;
                    int nd = d + 1;
                    if (nd == 4)
                        nd = 0;
 
                    nx = x + direct[nd][0];
                    ny = y + direct[nd][1];
                    if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                        if (!visit[nx][ny][nk]) {
                            q.add(new int[] { nx, ny, nk });
                            visit[nx][ny][nk] = true;
                        }
                    }
                }
            }
 
        }
 
        System.out.println("No");
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N][M];
        visit = new boolean[N][M][4];
        K = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            for (int j = 0; j < M; j++) {
                char ch = str.charAt(j);
                if (ch == 'U')
                    list[i][j] = 0;
                else if (ch == 'R')
                    list[i][j] = 1;
                else if (ch == 'D')
                    list[i][j] = 2;
                else
                    list[i][j] = 3;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 1012 유기농 배추  (0) 2021.02.03
boj 16956 늑대와 양  (0) 2021.02.03
boj 2638 치즈  (0) 2021.01.22
boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22

https://www.acmicpc.net/problem/2638

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표

www.acmicpc.net

2636번과 매우 유사한 문제입니다.

2636번과 다른점은 적어도 2변 이상이 공기와 인접해야 치즈가 녹는다는 점입니다.

가장자리에는 치즈가 없기때문에 0,0에서 bfs로 공기부분을 체크하고

반복문으로 치즈가 공기와 인접하는지 확인하고 2변 이상이 인접하면 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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int list[100][100], N, M;
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
bool visit[100][100];
 
void bfs() {
    memset(visit, false, sizeof(visit));
 
    queue<pair<int, int> > q;
    q.push({ 0,0 });
    visit[0][0] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (visit[nx][ny] || list[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!list[i][j]) continue;
 
            int cnt = 0;
            for (int x = 0; x < 4; x++) {
                int ni = i + direct[x][0];
                int nj = j + direct[x][1];
 
                if (visit[ni][nj]) cnt++;
            }
 
            if (cnt >= 2) list[i][j] = 0;
        }
    }
}
 
bool chk() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (list[i][j]) return true;
        }
    }
 
    return false;
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    for (int ans = 1; ; ans++) {
        bfs();
        func();
        if (!chk()) {
            cout << ans << '\n';
            break;
        }
    }
 
    return 0;
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 16956 늑대와 양  (0) 2021.02.03
boj 20419 화살표 미로 (Easy)  (0) 2021.01.23
boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22

https://www.acmicpc.net/problem/17142

 

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고

www.acmicpc.net

바이러스의 위치들을 저장해놓고 활성할 바이러스를 부르트포스로 정하여 bfs로 바이러스가 퍼지는 최소 시간을 구하는 문제입니다.

바이러스가 모두 퍼졌는지에 대한 확인은 처음 0의 갯수(zero) == 전염된 0의 갯수(viruson)으로 확인하였고,

7번 예제와 같이 입력 값으로 빈칸이 주어지지 않은 경우에는

예외처리로 벽의 갯수(wall) + 바이러스의 위치(virus.size()) == N*N으로 확인하였습니다.

마지막에 비활성화 바이러스만 남아도 모두 전염된 것으로 보기 때문에 d배열에서 해당 위치가 빈칸일 경우에만 시간비교를 하였습니다.

 

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
 
vector<pair<int, int> > virus, op;
int list[50][50], d[50][50], N, M, ans = -1, wall, viruson, zero;
int direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
bool visit[50][50], chk[10];
 
void bfs() {
    memset(d, 0, sizeof(d));
    memset(visit, false, sizeof(visit));
    viruson = 0;
 
    int virusoff = virus.size() - M;
    queue<pair<pair<int, int>, int> > q;
    for (int i = 0; i < op.size(); i++) {
        q.push({ op[i], 0 });
        visit[op[i].first][op[i].second] = true;
    }
 
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (list[nx][ny] == 1 || visit[nx][ny]) continue;
 
            q.push({ {nx,ny},cnt + 1 });
            visit[nx][ny] = true;
            d[nx][ny] = d[x][y] + 1;
            if (list[nx][ny] == 0) viruson++;
        }
    }
 
    if (zero == viruson) {
        int movetime = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (list[i][j]) continue;
 
                movetime = max(movetime, d[i][j]);
            }
        }
 
        if (ans == -1) ans = movetime;
        else ans = min(ans, movetime);
    }
}
 
void func(int idx, int cnt) {
    if (cnt == M) {
        bfs();        
        return;
    }
 
    for (int i = idx; i < virus.size(); i++){
        if (chk[i]) continue;
 
        op.push_back(virus[i]);
        chk[i] = true;
        func(i + 1, cnt + 1);
        chk[i] = false;
        op.pop_back();
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
            if (list[i][j] == 2) {
                virus.push_back({ i,j });
            }
            else if (list[i][j]) {
                wall++;
            }
            else zero++;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    if (wall + virus.size() == N*N) ans = 0;
    else func(0, 0);
    cout << ans << '\n';
 
    return 0;
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 20419 화살표 미로 (Easy)  (0) 2021.01.23
boj 2638 치즈  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22
boj 3055 탈출  (0) 2021.01.22

https://www.acmicpc.net/problem/2636

 

2636번: 치즈

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진

www.acmicpc.net

판의 가장자리에는 치즈가 없기 때문에 0,0에서 bfs로 탐색하여 공기 부분을 체크를 합니다.

그 후에 반복문으로 치즈가 있는 위치에 인접한 좌표에 공기가 있으면 0으로 바꿔줍니다.

이 과정을 반복하여 치즈가 모두 녹아 없어지는 데 걸린 시간을 구하면서 1시간 전에 남아있는 치즈조각의 갯수를 출력합니다.

(치즈를 한번 녹였을 때 남아있는 치즈조각의 갯수를 계속해서 갱신합니다.)

 

 

[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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int list[100][100], N, M, pre, ans;
int direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
bool visit[100][100];
 
void bfs() {
    memset(visit, false, sizeof(visit));
    queue<pair<int, int> > q;
    q.push({ 0,0 });
    visit[0][0] = true;
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (list[nx][ny] || visit[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    ans = pre;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            if (!list[i][j]) continue;
 
            for (int k = 0; k < 4; k++) {
                int nx = i + direct[k][0];
                int ny = j + direct[k][1];
 
                if (visit[nx][ny]) {
                    list[i][j] = 0;
                    ans--;
                    break;
                }
            }
        }
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
            if (list[i][j]) pre++;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    if (!pre) cout << "0\n0\n";
    for (int T = 1; pre ; T++) {
        bfs();
        func();
        if (!ans) {
            cout << T << '\n' << pre << '\n';
            break;
        }
 
        pre = ans;
    }
 
    return 0;
}
 cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[101][101];
    static boolean visit[][] = new boolean[101][101];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, cnt;
 
    static void removeCheese() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (list[i][j] == 1) {
                    boolean chk = false;
                    for (int d = 0; d < 4; d++) {
                        int nx = i + direct[d][0];
                        int ny = j + direct[d][1];
 
                        if (visit[nx][ny]) {
                            chk = true;
                            break;
                        }
                    }
 
                    if (chk) {
                        list[i][j] = 0;
                        cnt--;
                    }
                }
            }
        }
    }
 
    static void bfs() {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { 0, 0 });
        visit[0][0] = true;
 
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (visit[nx][ny] || list[nx][ny] == 1)
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
    }
 
    static void init() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(visit[i], false);
        }
    }
 
    static void func() {
        int pre = cnt;
        for (int t = 1;; t++) {
            bfs();
            removeCheese();
            init();
            if (cnt == 0) {
                System.out.println(t);
                System.out.println(pre);
                return;
            }
            pre = cnt;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == 1)
                    cnt++;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 2638 치즈  (0) 2021.01.22
boj 17142 연구소 3  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22
boj 3055 탈출  (0) 2021.01.22
boj 2234 성곽  (0) 2021.01.22

https://www.acmicpc.net/problem/1039

 

1039번: 교환

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

작년에 풀었을 때는 못풀었었는데 생각보다 간단한 bfs로 해결 가능한 문제였습니다.

 

이 문제는 swap(i번째 숫자, j번째 숫자)를 K번만큼 하였을 때 만들 수 있는 가장 큰 수를 출력하지만 K번의 연산을 할 수 없으면 -1을 출력해야합니다.

 

이 때, 바꾼수가 0으로 시작하면 안되기때문에 이에 대한 예외처리만 해주면 됩니다.

여기서 K번의 연산 후에 0으로 시작하는 수가 아닌 중간에도 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static boolean visit[][] = new boolean[1000001][11];
    static int N, K, ans = -1;
 
    static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { N, 0 });
        visit[N][0] = true;
 
        while (!q.isEmpty()) {
            int xx = q.peek()[0];
            char x[] = Integer.toString(xx).toCharArray();
            int cnt = q.peek()[1];
            q.remove();
 
            if (cnt == K) {
                ans = Math.max(ans, xx);
                continue;
            }
 
            char newx[];
            for (int i = 0; i < x.length; i++) {
                for (int j = i + 1; j < x.length; j++) {
                    if (i == 0 && x[j] == '0')
                        continue;
 
                    newx = x.clone();
                    char temp = newx[i];
                    newx[i] = newx[j];
                    newx[j] = temp;
 
                    int y = Integer.parseInt(String.valueOf(newx));
                    if (!visit[y][cnt + 1]) {
                        q.add(new int[] { y, cnt + 1 });
                        visit[y][cnt + 1] = true;
                    }
                }
            }
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
        System.out.println(ans);
    }
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 3055 탈출  (0) 2021.01.22
boj 2234 성곽  (0) 2021.01.22
boj 17472 다리 만들기 2  (0) 2021.01.22

 

https://www.acmicpc.net/problem/3055

 

3055번: 탈출

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제

www.acmicpc.net

두 종류의 bfs을 사용하여 해결하였습니다.

하나는 물에 대한 bfs,

하나는 고슴고치에 대한 bfs입니다.

 

[물이 흐르는 조건]

1. 돌을 통과할 수 없다.

2. 비버의 소굴로 이동할 수 없다.

 

[고슴도치가 이동하는 조건]

1. 돌을 통과할 수 없다.

2. 물로 차있는 구역으로 이동할 수 없다.

3. 물이 찰 예정인 칸으로 이동할 수 없다.

 

물이 찰 예정인 칸으로 이동할 수 없다는 말은 물과 고슴도치가 같은 시간에 같은 장소에 갈 수 없다는 것입니다.

 

따라서 물에 대한 bfs로 물이 먼저 흐르게 하고, 그 다음에 고슴도치에 대한 bfs로 고슴도치를 이동시키면 되는 문제입니다.

 

이 과정을 무한반복하여 고슴도치가 비버의 소굴로 이동하면 그 시간을 출력하고,

과정을 반복하던 도중에 고슴도치의 좌표가 들어있는 큐가 비어있으면 탈출에 실패했다는 것이니, "KAKTUS"를 출력합니다.

 

C++ 소스 추가하였습니다.

 

 

[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
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
#include <iostream>
#include <queue>
using namespace std;
 
queue<pair<int, int> > q;
queue<pair<int, int> > wq;
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
bool visit[51][51], wvisit[51][51], chk;
char list[51][51];
int N, M, ex, ey;
 
void waterbfs() {
    int qsize = wq.size();
    while (qsize--) {
        int x = wq.front().first;
        int y = wq.front().second;
        wq.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (wvisit[nx][ny] || list[nx][ny] == 'D' || list[nx][ny] == 'X') continue;
 
            wq.push({ nx,ny });
            wvisit[nx][ny] = true;
            list[nx][ny] = '*';
        }
    }
}
 
void bfs() {
    int qsize = q.size();
    while (qsize--) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (visit[nx][ny] || list[nx][ny] == 'X' || list[nx][ny] == '*') continue;
 
            if (list[nx][ny] == 'D') {
                chk = true;
                return;
            }
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void func() {
    for (int T = 1; ; T++) {
        waterbfs();
        bfs();
 
        if (chk) {
            cout << T << '\n';
            return;
        }
        else if (q.empty()) {
            cout << "KAKTUS\n";
            return;
        }
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
            if (list[i][j] == 'S') {
                q.push({ i,j });
                visit[i][j] = true;
            }
            else if (list[i][j] == 'D') {
                ex = i;
                ey = j;
            }
            else if (list[i][j] == '*') {
                wq.push({ i,j });
                visit[i][j] = true;
            }
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char list[][] = new char[50][50];
    static boolean qvisit[][] = new boolean[50][50];
    static boolean wvisit[][] = new boolean[50][50];
    static int N, M, ex, ey;
    static Queue<int[]> q = new LinkedList<>();
    static Queue<int[]> w = new LinkedList<>();
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
 
    static void waterbfs() {
        int size = w.size();
        while (size-- > 0) {
            int x=w.peek()[0];
            int y=w.peek()[1];
            w.remove();
            
            for(int i=0; i<4; i++) {
                int nx=x+direct[i][0];
                int ny=y+direct[i][1];
                
                if(nx<0 || ny<0 || nx>=N || ny>=M)
                    continue;
                if(wvisit[nx][ny] || list[nx][ny]=='X' || list[nx][ny]=='D')
                    continue;
                
                w.add(new int[] {nx,ny});
                wvisit[nx][ny]=true;
            }
        }
    }
 
    static boolean bfs() {
        int size=q.size();
        while(size-->0) {
            int x=q.peek()[0];
            int y=q.peek()[1];
            q.remove();
            
            for(int i=0; i<4; i++) {
                int nx=x+direct[i][0];
                int ny=y+direct[i][1];
                
                if(nx<0 || ny<0 || nx>=N || ny>=M)
                    continue;
                if(qvisit[nx][ny] || wvisit[nx][ny] || list[nx][ny]=='X')
                    continue;
                if(nx==ex && ny==ey) 
                    return true;
                
                q.add(new int[] {nx,ny});
                qvisit[nx][ny]=true;
            }
        }
        return false;
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            for (int j = 0; j < M; j++) {
                char ch = list[i][j];
                if (ch == 'S') {
                    q.add(new int[] { i, j });
                    qvisit[i][j] = true;
                } else if (ch == '*') {
                    w.add(new int[] { i, j });
                    wvisit[i][j] = true;
                } else if (ch == 'D') {
                    ex = i;
                    ey = j;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        for(int T=1; ; T++) {
            waterbfs();
            if(bfs()) {
                System.out.println(T);
                break;
            }
            
            if(q.isEmpty()) {
                System.out.println("KAKTUS");
                break;
            }
        }
    }
}
 
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22
boj 2234 성곽  (0) 2021.01.22
boj 17472 다리 만들기 2  (0) 2021.01.22

https://www.acmicpc.net/problem/2234

 

2234번: 성곽

첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를,

www.acmicpc.net

저는 두 번의 bfs를 사용하였습니다.

한번은 각 방의 넘버링을 위한 bfs, 다른 한번은 각 방에 인접한 방을 찾기 위한 bfs입니다.

 

최종으로 구해야 할 것이

1. 이 성에 있는 방의 개수

2. 가장 넓은 방의 넓이

3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

이렇게 됩니다.

저는 1, 2번은 각 방의 넘버링으로 해결하였고, 3번은 각 방에 인접한 방을 찾아서 해결하였습니다.

 

 

이 문제에서 입력으로 주어지는 숫자는 벽에 대한 정보입니다.

서쪽에 벽이 있으면 1, 북쪽에 벽이 있으면 2, 동쪽에 벽이 있으면 4, 남쪽에 벽이 있으면 8을 더한 값이 주어집니다.

만약에 벽이 없으면 하나도 더해지지 않은 0이 주어질 것이고, 사방에 모두 벽이 있으면 1 + 2 + 4 + 8 = 15가 주어질 것입니다.

 

1, 2, 4, 8을 더한 값이 주어지기 때문에 먼저 비트마스킹을 떠올렸습니다.

벽을 체크하기 위해 wall 배열에 해당 방향에 대한 값을 넣었고,

해당 방향을 체크할 때 해당하는 값인 wall[i]과 list[x][y]를 비교하여

list[x][y] & wall[i]이 0이면 벽이 없는 것이고, 0이 아니면 벽이 있는 것이라고 보시면 되겠습니다.

 

bfs & 비트마스킹으로 각 방에 넘버링을 하였고, 넘버링을 하면서 방의 크기도 같이 구하였습니다.

그 다음 bfs를 한번 더 돌려서 인접한 방 번호를 sideroom에 넣었고 방의 크기 + 인접한 방의 크기를 비교하여 최댓값을 출력하였습니다.

(sideroom을 set으로 한 이유는 중복체크를 하기 위함입니다.)

 

 

[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
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
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
 
set<int> sideroom[2501];
int N, M, wall[4] = { 4, 8, 1, 2 };
int list[50][50], direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
int roomnum, maxroomsize, Room[50][50], Roomsize[2501];
bool visit[50][50];
 
void sidechk(int sx, int sy, int num) {
    queue<pair<int, int> > q;
    q.push({ sx, sy });
    visit[sx][sy] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (Room[nx][ny] != num) {
                sideroom[num].insert(Room[nx][ny]);
                continue;
            }
            if (visit[nx][ny]) continue;
 
            q.push({ nx, ny });
            visit[nx][ny] = true;
        }
    }
}
 
void bfs(int sx, int sy, int num) {
    queue<pair<int, int> > q;
    q.push({ sx, sy });
    visit[sx][sy] = true;
    for (int t = 1; ; t++) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        Room[x][y] = num;
 
        for (int i = 0; i < 4; i++) {
            if (wall[i] & list[x][y]) continue;
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (visit[nx][ny]) continue;
            q.push({ nx, ny });
            visit[nx][ny] = true;
        }
 
        if (q.empty()) {
            Roomsize[num] = t;
            maxroomsize = max(maxroomsize, t);
            break;
        }
    }
}
 
void solve() {
    int maxroomsum = 0;
    cout << roomnum << '\n' << maxroomsize << '\n';
    for (int i = 1; i <= roomnum; i++) {
        set<int>:: iterator iter;
        for (iter = sideroom[i].begin(); iter != sideroom[i].end(); iter++) {
            int s = *iter;
 
            maxroomsum = max(maxroomsum, Roomsize[i] + Roomsize[s]);
        }
    }
 
    cout << maxroomsum << '\n';
}
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visit[i][j]) continue;
            bfs(i, j, ++roomnum);
        }
    }
    memset(visit, false, sizeof(visit));
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visit[i][j]) continue;
            sidechk(i, j, Room[i][j]);
        }
    }
}
 
void input() {
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
    solve();
 
    return 0;
}
 cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[51][51];
    static int div[][] = new int[51][51];
    static boolean visit[][] = new boolean[51][51];
    static ArrayList<Integer> roomarea = new ArrayList<>();
    static Set<Integer> s[];
    static int wall[] = { 4, 8, 1, 2 };
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, roomcnt, maxarea, cnt, ans;
 
    static void sidechk(int sx, int sy) {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { sx, sy });
        visit[sx][sy] = true;
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (visit[nx][ny])
                    continue;
 
                if (div[x][y] != div[nx][ny])
                    s[div[x][y]].add(div[nx][ny]);
                else {
                    dq.add(new int[] { nx, ny });
                    visit[nx][ny] = true;
                }
            }
        }
    }
 
    static void solveroom(int sx, int sy) {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { sx, sy });
        visit[sx][sy] = true;
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
            div[x][y] = roomcnt;
            cnt++;
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (visit[nx][ny] || (wall[i] & list[x][y]) > 0)
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
    }
 
    static void func() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visit[i][j])
                    continue;
                solveroom(i, j);
                roomarea.add(cnt);
                roomcnt++;
                maxarea = Math.max(maxarea, cnt);
                cnt = 0;
            }
        }
 
        s = new HashSet[roomcnt];
        for (int i = 0; i < roomcnt; i++)
            s[i] = new HashSet<>();
 
        for (int i = 0; i < N; i++)
            Arrays.fill(visit[i], false);
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visit[i][j])
                    continue;
 
                sidechk(i, j);
            }
        }
    }
 
    static void solve() {
        for (int i = 0; i < roomcnt; i++) {
            Iterator<Integer> iter = s[i].iterator();
            while (iter.hasNext()) {
                ans = Math.max(ans, roomarea.get(i) + roomarea.get(iter.next()));
            }
        }
 
        System.out.println(roomcnt + "\n" + maxarea + "\n" + ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        solve();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22
boj 3055 탈출  (0) 2021.01.22
boj 17472 다리 만들기 2  (0) 2021.01.22

 

https://www.acmicpc.net/problem/17472

 

17472번: 다리 만들기 2

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

www.acmicpc.net

BFS + MST 로 해결하는 문제입니다.

 

먼저 섬의 번호를 구분할 수 있게 표시하고,

섬의 한 지점에서 한방향으로 탐색을 하여 길이가 2이상인 다리를 놓을수 있는지 확인합니다.

 

놓을 수 있으면 시작 섬 번호, 도착 섬 번호, 길이를 벡터에 push_back을 하고,

길이가 2 미만이거나 놓을 수 없으면 빠져나와줍니다.

(여기서 chk 배열을 사용한건

섬 1에서 섬 2까지 연결하는데 같은길이의 다리를 2개 이상 놓을 수 있는 경우와

섬 1에서 섬 2까지 연결하는 것과 섬 2에서 섬 1까지 연결하는 것이 중복되기 때문에 사용하였습니다.)

 

이제 시작 섬 번호, 도착 섬 번호, 길이 정보가 담겨있는 벡터를 길이가 작은 순서대로 sort를 한 후에

크루스칼 알고리즘에서 작은 간선을 선택하는 방식처럼 작은 길이를 선택해주면서 parent 배열을 갱신합니다.

(parent 배열에는 해당 번호 섬의 root가 되는 섬의 번호가 저장되어 있으며, 어떤 섬과 연결되어 있는지 알 수 있습니다.)

 

ans가 0이면 -1을 출력하고 끝내면 되고, 아니면 답을 출력하면 되는데

중요한 것은 모든섬을 연결해야 한다는 것입니다. (그거 때문에 왜틀렸는지 오랫동안 고민해서 ㅠㅠ)

섬이 최대 6개이므로 선형으로 root가 같은지 체크를 한 후에 정답을 출력합니다.

 
1 6
1 0 0 1 0 1
 
//ans : -1
cs

 

문제풀이 하면서 찾은 반례 던지고 갑니다.

 

 

[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
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
typedef struct edge {
    int s;
    int e;
    int d;
}edge;
 
vector<edge> v;
int parent[11], N, M, ans, areadiv;
int list[10][10], direct[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
bool visit[10][10], chk[10][10][10];
 
bool cmp(edge a, edge b) {
    return a.d < b.d;
}
 
int find_parent(int u) {
    if (parent[u] == u) return u;
 
    return parent[u] = find_parent(parent[u]);
}
 
void union_find(int a, int b) {
    int aroot = find_parent(a);
    int broot = find_parent(b);
 
    parent[max(aroot, broot)] = min(aroot, broot);
}
 
void func() {
    for (int i = 0; i < v.size(); i++) {
        int s = v[i].s;
        int e = v[i].e;
        
        int sroot = find_parent(s);
        int eroot = find_parent(e);
 
        if (sroot == eroot) continue;
 
        union_find(sroot, eroot);
        ans += v[i].d;
    }
 
    if (!ans) {
        cout << "-1\n";
        return;
    }
 
    int root = find_parent(1);
    for (int i = 2; i <= areadiv; i++) {
        int next = find_parent(i);
        if (root != next) {
            ans = -1;
            break;
        }
    }
    cout << ans << '\n';
}
 
void dist(int x, int y, int di, int sn) {
    int xx = x;
    int yy = y;
    int cnt = 0;
 
    while (1) {
        int nx = xx + direct[di][0];
        int ny = yy + direct[di][1];
        
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) break;
        if (list[nx][ny] == sn) break;
        if (!list[nx][ny]) {
            cnt++;
            xx = nx;
            yy = ny;
        }
        else if (list[nx][ny] != sn) {
            if (cnt < 2) break;
            if (chk[sn][list[nx][ny]][cnt] || chk[list[nx][ny]][sn][cnt]) break;
            chk[sn][list[nx][ny]][cnt] = true;
            chk[list[nx][ny]][sn][cnt] = true;
            v.push_back({ sn, list[nx][ny], cnt });
            break;
        }
    }
 
    return;
}
 
void find_dist() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (list[i][j]) {
                for (int k = 0; k < 4; k++) {
                    dist(i, j, k, list[i][j]);
                }
            }
        }
    }
 
    sort(v.begin(), v.end(), cmp);
}
 
void bfs(int sx, int sy, int num) {
    queue<pair<int, int> > q;
    q.push({ sx,sy });
    visit[sx][sy] = true;
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        list[x][y] = num;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (!list[nx][ny] || visit[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
         }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visit[i][j] || !list[i][j]) continue;
 
            bfs(i, j, ++areadiv);
        }
    }
    for (int i = 1; i <= areadiv; i++) {
        parent[i] = i;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    find_dist();
    func();
 
    return 0;
}
 cs

 

 

[Java]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<int[]> edge = new ArrayList<>();
    static int list[][] = new int[11][11];
    static boolean visit[][] = new boolean[11][11];
    static boolean chk[][][] = new boolean[7][7][11];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int parent[] = new int[7];
    static int N, M, cnt, div, ans;
 
    static int find(int v) {
        if (parent[v] == v)
            return v;
        return parent[v] = find(parent[v]);
    }
 
    static void Union(int u, int v, int w) {
        int a = find(u);
        int b = find(v);
 
        if (a == b)
            return;
 
        parent[b] = a;
        cnt++;
        ans += w;
    }
 
    static void solve() {
        Collections.sort(edge, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });
 
        for (int i = 0; i < edge.size(); i++) {
            int x = edge.get(i)[0];
            int y = edge.get(i)[1];
            int dis = edge.get(i)[2];
 
            Union(x, y, dis);
        }
 
        if (cnt != div - 1)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
 
    static void getDist(int sx, int sy, int d, int num) {
        int x = sx;
        int y = sy;
        int cnt = 0;
        while (true) {
            x += direct[d][0];
            y += direct[d][1];
            cnt++;
 
            if (x < 1 || y < 1 || x > N || y > M)
                break;
            if (list[x][y] == num)
                break;
            if (list[x][y] == 0)
                continue;
            if (list[x][y] != num) {
                if (cnt <= 2)
                    break;
                if (chk[num][list[x][y]][cnt])
                    break;
                chk[num][list[x][y]][cnt] = true;
                chk[list[x][y]][num][cnt] = true;
                edge.add(new int[] { num, list[x][y], cnt - 1 });
                return;
            }
        }
    }
 
    static void dist() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (list[i][j] != 0) {
                    for (int k = 0; k < 4; k++) {
                        getDist(i, j, k, list[i][j]);
                    }
                }
            }
        }
    }
 
    static void init() {
        for (int i = 1; i <= div; i++) {
            parent[i] = i;
        }
    }
 
    static void bfs(int sx, int sy) {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { sx, sy });
        visit[sx][sy] = true;
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
 
            list[x][y] = div;
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 1 || ny < 1 || nx > N || ny > M)
                    continue;
                if (visit[nx][ny] || list[nx][ny] == 0)
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
    }
 
    static void func() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (visit[i][j] || list[i][j] == 0)
                    continue;
 
                div++;
                bfs(i, j);
            }
        }
 
        init();
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        dist();
        solve();
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22
boj 1039 교환  (0) 2021.01.22
boj 3055 탈출  (0) 2021.01.22
boj 2234 성곽  (0) 2021.01.22

+ Recent posts

티스토리툴바