[백준][자바][2234 성곽]

...이거 중복이 없다

문제를 보니 비트마스크 연산을 이용하는 거 같은데 

처음이라 골치가 아팠다

내가 맨처음 생각 문제는 현재 내가 보고 있는 배열이랑 옆에 이동할 배열이랑

벽이 중복되서

예를 들어 

현재  방이 11이란 값일경우 이렇게 되있고

ㅡ

|

ㅡ 

다음 우측도 11 같은 경우는 

ㅡ

|

ㅡ

 어떻게 할건가란 생각에 고민하다가 다른 분들 풀이를 검색하는데...

아무리 봐도 이런부분에 대한 처리가 안되어있었다

...뭐지...겁나게 고민하고 머리를 굴려보다가...생각해보니...

설마 중복 된다는 말이 있었나 하고 찾아보니...아..

글쿠나 없네...ㅎ

저번에 풀던 문제랑 착각중인것이다.ㅎ...

하...일단 풀자 ..ㅠ.

package backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
class room_Point{
	int x;
	int y;
	room_Point(int y, int x ){
		this.y = y; 
		this.x = x; 
	}
}
public class Main_backjoon_2234_성곽 {
	static int N; 
	static int M;
	static Map
 mappingMapCount = new HashMap();
	static int map[][] = new int[50][50];
	static int tempMap[][] = new int[50][50];
	static int wall[] = {8, 4, 2, 1};
	static boolean visited[][] = new boolean[50][50];
	static Queue q = new LinkedList(); 
	//하 우 상 좌
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int break_maxRoomCount = 0;
	static int castle_roomCount = 0;
	static int maxRoomCount = 0;
	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() );	
		for(int i = 0 ; i < M ; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int idx = 0 ;
			while( st.hasMoreTokens() ) {
				map[i][idx++] =  Integer.parseInt( st.nextToken() );
			}
		}
		
		
		/* solve */ 
		int map_Number = 0;
		for(int i = 0 ; i < M; i++) {
			for(int j =0 ; j < N ; j++) {
				/*만약 사방이 막힌 방 이라면 */
				if(map[i][j] == 15) {
					 visited[i][j] = true;
					 tempMap[i][j] = map_Number;
					 mappingMapCount.put(map_Number, 1);
					 map_Number += 1;
					 maxRoomCount = Math.max( maxRoomCount, 1 );
					 castle_roomCount += 1;
					 continue;
				}
				if(!visited[i][j]) { 
					q.add(new room_Point(i, j));
					bfs(map_Number++);
				}
			}
		}

		/* 브레이킹 카운트  */
		for(int i = 0 ; i < M; i++) {
			for(int j =0 ; j < N ; j++) {
				breakWall_RoomCount(i,j);
			}
		}
		
		System.out.println(castle_roomCount);
		System.out.println(maxRoomCount);
		System.out.println(break_maxRoomCount);
	}
	public static void bfs(int map_Number) {
		int roomCount = 1;
		boolean flag = false;
		while(!q.isEmpty()) {
			room_Point rp = q.poll();
			int garo = rp.x;
			int sero = rp.y;	
			visited[sero][garo] = true;
			tempMap[sero][garo] = map_Number;
			for (int i = 0; i < 4 ; i++) {
				//사방이 막힌 방 하나 일 떄 
				if( detect_Wall( sero, garo, i ) ) {
					int xx = dx[i] + garo;
					int yy = dy[i] + sero;
					//범위안이면서 도 
					if( xx >= 0 &&  xx < N && yy >= 0 && yy < M ) {
							//방문을 안했으면
							if ( !visited[yy][xx] ) {
								 visited[yy][xx] = true;
								 tempMap[yy][xx] = map_Number; // 새로운 배열에 맵 위치를 찍음 
								 q.add( new room_Point(yy, xx) );
								 flag = true;
								 roomCount++; /*현재 방안에 있는 roomCount */					
							}						
					}
				}
			}
		}
		
		if( flag ) {
			mappingMapCount.put(map_Number, roomCount); /*현재 맵 넘버 , 방  개수*/
			maxRoomCount = Math.max( maxRoomCount, roomCount );
			castle_roomCount += 1; 
		}
	}
	
	/*3번 answer 계산
	 * tempMap에서 상단 하단 검사하면서 다른 방인경우
	 * 지금 방 카운트, 다른 방 카운트를 맵을 이용해서 계산 
	 */
	public static void breakWall_RoomCount(int sero, int garo) {
		for (int i = 0; i < 2; i ++ ) {
			int xx = dx[i] + garo ;
			int yy = dy[i] + sero ;
			if( xx >= 0 &&  xx < N && yy >= 0 && yy < M ) { 
				if(tempMap[sero][garo] != tempMap[yy][xx]) {
					int firstmapCount = mappingMapCount.get(tempMap[sero][garo]) ;
					int nextmapCount = mappingMapCount.get(tempMap[yy][xx]) ;
					break_maxRoomCount = Math.max(break_maxRoomCount ,(firstmapCount + nextmapCount));
				}
			}
		}
	}

	/* 현재값이랑 하나씩 and 연산, 어디가 뚫려있는지 검사 */
	public static boolean detect_Wall(int y, int x, int idx) {
		if( ( map[y][x] & wall[idx] ) > 0 ) {
			return false; 
		}else {
			return true;
		}
	}
	
		
		
}

하...풀었다...

5시간 걸렸다..ㅋㅋㅋㅋ...

문제 이해를 잘못해서 한 두시간 버리고,,그런것 같다

역시 문제는 풀고나면 별거 아닌데...

중간중간 고비가 있는거 같다. 못 푸는 문제가 아닐까 싶은.?

문제 자체 이해가 어렵지 사실 다른 bfs 문제랑 별반 다를 게 없다 .

이 문제에서 아웃풋이 3개인데

1. 이 성에 있는 방의 개수

2. 가장 넒은 방의 개수 

3. 하나의 벽을 제거해서 얻을 수 있는 가장 넒은 방의 수

1~3 까지 하나씩 차근 차근 풀어가면된다

나는 이런 비트마스크? 문제는 처음인데 솔직히 겁났다.

굉장히 복잡해보여서 

차근차근 풀어보니 그냥...이해하고 풀면 된다.

이 문제는 예를 들어 15가 주어진 경우

2진수로 바꾸면 1111이다.

11인 경우는 1011 이런식으로 생각하면된다

여기서 하, 우 , 상, 좌 이런식으로 벽이 있으면 8,4,2,1 이렇게 값이 주어지는데 

 detect_Wall이란 함수를 통해서 어디가 뚫려있는지 검사한다

and 연산을 통해서 쉽게 구할수 있는데 

11 = 1011 인경우

1011

1000  하단

-----

1000

1011

0100 우측

-----

0000

1011

0010 상단

-----

0010

1011

0001 좌측

-----

0001

이런식으로 진행된다 여기서 전체가 0인 친구를 보자 

우측에 해당 되는 비트와 and 연산을 진행했다.

우측이 뚫려있단 이야기이다 .

나는 이걸 반대로 생각해서 ... 한시간? 정도 더 날렸다..ㅋㅋㅋㅋ

사실 뭐 이런 and 연산을 안해도 그냥 포문으로 4개 검사해도 될듯 싶다.

여튼 

bfs를 이용해서 방의 개수, 가장 넒은 방의 개수를 구할수 있다.

그렇다면 이제 마지막 벽 제거 후 방 갯수를 구하는 것만 남았는데

이중 포문 후에 우측, 하단 부분을 하나씩 제거해가면서 개수를 구하면 되겠다

그러나 그런경우 꽤나 많은 연산처리를 겪게 되니 

예외처리를 넣어줘야할것같았다.

그런데 내가 구현해놓은 부분엔 그런부분이 없어

temp_Map 배열을 하나만들어놓고 , 방마다 번호를 지정해 다르게 찍어 주었다.

그리고 Map을 이용해서 방마다 방의 개수를 입력해 놓은 후 

포문을 돌아가며 우측, 하단 부분 검색시 현재의 방이 아닌 다른 방이면 

더해서 최대값을 갱신하게 했다.

문제는 풀면 재밌는데..디버깅 과정이 고된것 같다..주륵..ㅠ