[백준] 2234번 성곽

생각

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는
통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

처음 생각

기존에 보던 미로 찾기와 다르게 방에대해서 벽의 조건을 주는 문제이다. 따라서 방 마다 상 하 좌 우로 갈 수 있는지 알아내기 위해서 Pair class를 만들어서 사용하였다.

다음 생각

또 특이하게 갈 수 있는 길을 그냥 주지 않고 각각 1 2 4 8의 값을 매겨 더한 값을 준다. 문제에 힌트로 이진수라 생각하면 편하다 되어있으므로 수를 받아서 이를 이진수로 변환하여 갈 수 있는길 아닌길을 판단해 주었다.

다다음 생각

우선 조건들 받기를 성공했다면 탐색을 통해서 1) 방의 개수 와 2) 제일 큰 방의 크기는 바로 알아낼 수 있었다. 문제가 되는건 3) 한 쪽 벽면을 허물 수 있을 때, 최대 방의 크기 였다.

다다다음 생각

우선 생각한 방법은 만들어둔 Pair class에 방의 번호를 넣을 변수를 추가하여 해당 방을 하나 탐색할 때마다 전역변수를 늘려가며(방의 개수를 위해서 만들어둠) 해당 번호를 다 넣어주었다. 그리고 처음부터 방이 몇개인지 알 수 없으니 List를 하나 만들어서 앞에서 쓴 방의 변수를 index로 해당 방의 크기를 넣어주었다.

다다다다음 생각

이후, 1차적인 방의 개수와 제일 큰 방의 크기를 위한 탐색이 다 끝나면 다시 배열의 0,0부터 완전 탐색을 시작하고 해당 방에서 벽이 있는 곳을 확인하여 벽 너머가 위에서 만들어둔 변수 방의 번호와 다르다면 list에서 해당 방들의 값을 가져와 더해주고 이 값의 최대를 구하였다.

방안

1) Integer.toBinaryString() 을 사용하여 이진 수 값을 얻었다.

2) 배열 타입을 Pair로 지정해서 사용했지만 두 방의 합친 크기를 위한 배열은 방을 탐색하면서 int 타입 배열로 방의 번호를 채워넣어 주면서 진행해도 됐을 것 같다 주변의 방의 번호가 다르다면 어차피 벽이 있었다는 뜻이기 때문이다.

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 167 168 169 170 171 172 173 174 175

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.StringTokenizer;   public class Main{     static int n,m;     static Pair[][] arr;     public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         n = Integer.parseInt(st.nextToken());         m = Integer.parseInt(st.nextToken());         arr = new Pair[m][n];         // 1 1 1 1 => 0 ~ 15         // 남 동 북 서         for(int i=0;i<m;i++) {             st = new StringTokenizer(br.readLine());             for(int j=0;j<n;j++) {                 // 2진수로 변화해서 뒤(1) 부터 보자.                 String t = Integer.toBinaryString(Integer.parseInt(st.nextToken()));                 Pair tt = new Pair(0, 0, 0, 0,i,j,0);                 for(int k=t.length()-1;k>=0;k--) {                     if(t.charAt(k)=='1') {                         switch((int)Math.pow(2, t.length()-1-k)){                             case 1: // 서                                 tt.s = 1;                                 break;                             case 2: // 북                                 tt.b = 1;                                 break;                             case 4: // 동                                 tt.d = 1;                                 break;                             case 8: // 남                                 tt.n = 1;                                 break;                         }                     }                 }                 arr[i][j] = tt;             }         }         visited = new boolean[m][n];         // 방 개수 및 가장 큰 방 구하기         for(int i=0;i<m;i++) {             for(int j=0;j<n;j++) {                 // 방문 안한곳 체크해주기                 if(!visited[i][j]) {                     list.add(solve(i,j));                 }             }         }         // 벽을 부셨을 때 가장 큰 방 구하기         for(int i=0;i<m;i++) {             for(int j=0;j<n;j++)                 solve2(i,j);         }         System.out.println(totalRoom);         System.out.println(maxRoom);         System.out.println(plusMax);     }          // 2개 방의 합 최대 값과 방 번호에 따른 크기를 가지고 있는 List     static int plusMax;     static List<Integer> list = new ArrayList<>();     private static void solve2(int x,int y) {         // 4방향을 보고 벽인 방향 너머가 다른 방일 경우 더해준 값의 max를 구하자         Pair t = arr[x][y];         int cnt = list.get(t.rN);         for(int i=0;i<4;i++) {             int tx = t.x+dir[i][0];             int ty = t.y+dir[i][1];             if(tx<0 || ty<0 || tx>=m || ty>=n) continue;             switch(i) {             case 0: // 남                 if(t.n==1) {                     // 룸 넘버가 다를 경우 두 방을 합쳐주자.                     if(t.rN != arr[tx][ty].rN)                         plusMax = Math.max(plusMax,cnt+list.get(arr[tx][ty].rN));                 }                 break;             case 1: // 동                 if(t.d==1) {                     if(t.rN != arr[tx][ty].rN)                         plusMax = Math.max(plusMax,cnt+list.get(arr[tx][ty].rN));                 }                 break;             case 2: // 북                 if(t.b==1) {                     if(t.rN != arr[tx][ty].rN)                         plusMax = Math.max(plusMax,cnt+list.get(arr[tx][ty].rN));                 }                 break;             case 3: // 서                 if(t.s==1) {                     if(t.rN != arr[tx][ty].rN)                         plusMax = Math.max(plusMax,cnt+list.get(arr[tx][ty].rN));                 }                 break;             }         }     }          static int maxRoom,totalRoom;     static boolean[][] visited;     static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};     private static int solve(int x,int y) {         int nRoom = 0;         arr[x][y].rN = totalRoom;         Queue<Pair> queue = new LinkedList<>();         queue.add(new Pair(arr[x][y].d, arr[x][y].s, arr[x][y].n, arr[x][y].b,x,y,totalRoom));         visited[x][y] = true;         while(!queue.isEmpty()) {             Pair t = queue.poll();             nRoom++;             // 남 동 서 북 으로 이동 가능하면 이동             for(int i=0;i<4;i++) {                 int tx = t.x+dir[i][0];                 int ty = t.y+dir[i][1];                 if(tx<0 || ty<0 || tx>=m || ty>=n) continue;                 if(visited[tx][ty]) continue;                 arr[tx][ty].rN = totalRoom;                 switch(i) {                 case 0: // 남                     if(t.n==0) {                         queue.add(arr[tx][ty]);                         visited[tx][ty] = true;                     }                     break;                 case 1: // 동                     if(t.d==0) {                         queue.add(arr[tx][ty]);                         visited[tx][ty] = true;                     }                     break;                 case 2: // 북                     if(t.b==0) {                         queue.add(arr[tx][ty]);                         visited[tx][ty] = true;                     }                     break;                 case 3: // 서                     if(t.s==0) {                         queue.add(arr[tx][ty]);                         visited[tx][ty] = true;                     }                     break;                 }             }         }         // 가장 넓은 방 크기 구하기.         maxRoom = Math.max(maxRoom, nRoom);         // 방 개수 올리기.         totalRoom++;         return nRoom;     }          static class Pair{         int d,s,n,b,x,y,rN;         public Pair(int d,int s,int n,int b,int x,int y,int rN) {             this.d = d;             this.s = s;             this.n = n;             this.b = b;             this.x = x;             this.y = y;             this.rN = rN;         }     } } Colored by Color Scripter

cs