카테고리 없음

백준 2234 - 성곽

jin_j_i_n 2021. 5. 19. 20:28

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

 

2234번: 성곽

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

www.acmicpc.net

 

이건뭐

시키는대로 하면 되는 문제

 

이동가능한지아닌지는 비트연산으로 판단하면 될 것 같다

 

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
package algorithm;
 
import java.io.*;
import java.util.*;
public class B2234 {
    //위 , 아래 , 오 , 왼 
    static int[] dx = {-1,+1,0,0};     
    static int[] dy = {0,0,+1,-1}; 
    static int N; 
    static int M;
    static int count = 0;
    static boolean[][] visit;
    static int[][] board;
    static int[][] number;
    public static class Point {
        int x ; int y;
        public Point(int x, int y ) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static boolean moving(int room , int dir ) {
        boolean isOk = true;    
        for(int j = 0 ; j < 4; j++) {
            if((room & (1<<j)) > 0 ) {
                //벽이 있을 때 
                //서쪽에 있다면 동쪽에서 이동해야하고 
                //남쪽에 있다면 위쪽에서 이동
                //동쪽에 있담녀 서쪾에서 이동
                //북쪽에 있다면 남쪽에서 이동
                if(j == 0 ) { //벽 : 쪽에 있을때 
                    if (dir == 2 ) isOk = false;
                }else if(j == 1 ) { //북
                    if(dir == 1) isOk = false;
                }else if (j == 2 ) { //동 
                    if(dir == 3 )isOk = false;
                }else {
                    if(dir == 0) isOk = false;
                }
            }
        }
        return isOk;
    }
    
    public static boolean check(int x, int y ) {
        return x >= 0 && x < M && y>=0 && y < N;
    }
    
    public static void bfs(Point p) {
        count++;
        Queue<Point> que = new LinkedList<Point>();
        que.add(p);
        visit[p.x][p.y] = true;
        number[p.x][p.y] = count; 
        while(!que.isEmpty() ) {
            Point tmp = que.poll();
            int x = tmp.x ; int y = tmp.y;
            for(int i = 0 ; i < 4 ; i++ ) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(check(nx,ny )) {
                    if(moving(board[nx][ny] , i )) {
                        if(!visit[nx][ny]) {
                            visit[nx][ny] = true;
                            number[nx][ny] = count;
                            que.add(new Point(nx,ny));
                        }
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);
        
        board = new int[M][N];
        number = new int[M][N];
        visit = new boolean[M][N];
        
        for(int i = 0; i < M ; i++ ) {
            inputs = br.readLine().split(" ");
            for(int j = 0 ; j< N ; j++) {
                board[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        
        for(int i = 0; i < M ; i++ ) {            
            for(int j = 0 ; j< N ; j++) {
                if(!visit[i][j]) {
                    bfs(new Point(i,j));
                }
            }
        }
        
        HashMap<Integer , Integer> map = new HashMap<>();
        for(int i = 0; i < M ; i++ ) {            
            for(int j = 0 ; j< N ; j++) {
                if(!map.containsKey(number[i][j])) {
                    //아직 넓이가 없을 때
                    map.put(number[i][j], 1);
                }else {
                    int cur = map.get(number[i][j]);
                    cur += 1;
                    map.put(number[i][j],cur);
                }
            }
        }
        int max = 0;
        for(int i = 1; i<= count ; i++ ) {
            max = Math.max(max, map.get(i));
        }
        
        int sumMax = 0;
        for(int i = 0; i < M ; i++ ) {            
            for(int j = 0 ; j< N ; j++) {
                for(int k = 0 ; k < 4 ; k++ ) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (check(nx,ny)) {
                        if(number[nx][ny] != number[i][j]) {
                            sumMax = Math.max(sumMax, map.get(number[i][j]) + map.get(number[nx][ny]));
                        }
                    }
                }
            }
        }
        
        System.out.println(count);
        System.out.println(max);
        System.out.println(sumMax);
    }
}
 
cs