[백준] code.plus(BFS 알고리즘,JAVA)2234번, 성곽

문제 링크

2234번: 성곽

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 성곽에 각 방은 벽으로 막혀있습니다.

2. 방의 개수, 방의 최대 넓이, 벽을 1개 부술 때 방의 최대 넓이를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. BFS 탐색으로 성곽에 존재하는 방들의 넓이와 번호를 부여합니다.

 

2. 각 방에서 인접한 방에 넓이를 더한 최대값으로 벽을 1개 부술 때 최대 넓이를 구합니다.

 

 

공간에 벽이 존재하는 경우를 비트의 형태로 주어집니다.

 

0001 : 서쪽

 

0010 : 북쪽

 

0100 : 동쪽

 

1000 : 남쪽

 

예를들어 공간의 값이 11일 때

 

1011 :남쪽, 북쪽, 서쪽에 벽이 존재한다.

 

동서남북에 벽이 존재하는지 확인할 때

 

예를 들어 공간에 값이 11이고 동쪽에 벽이 있는지 확인할 때

 

1011 & 0100 = 0000(동쪽에 벽이 존재하지 않는다.)

 

다른 방향도 동일하게 AND(&)를 취하면 벽이 존재하는지 확인할 수 있습니다.

※AND의 결과가 0이면 벽이 X, 0이 아니면 벽O

 

북쪽 확인시

 

1011 & 0010 = 0010(0이 아니기 때문에 벽O)

 

 

예제입력 1.

 

1. BFS 탐색으로 성곽에 존재하는 방들의 넓이와 번호를 부여합니다.

1	1	2	2	4	4	4
1	1	1	2	4	5	4
1	1	1	3	4	3	4
1	3	3	3	3	3	4

방 1의 넓이 : 9

방 2의 넓이 : 3

방 3의 넓이 : 7

방 4의 넓이 : 8

방 5의 넓이 : 1

 

2. 각 방에서 인접한 방에 넓이를 더한 최대값으로 벽을 1개 부술 때 최대 넓이를 구합니다.

1	1	2	2	4	4	4
1	1	1	2	4	5	4
1	1	1	3	4	3	4
1	3	3	3	3	3	4

1 - 2 : 9 + 3 = 12

1 - 3 : 9 + 7 = 16

2 - 4 : 3 + 8 = 11

2 - 3 : 3 + 7 = 10

3 - 4 : 7 + 8 = 15

3 - 5 : 7 + 1 = 8

4 - 5 : 8 + 1 = 9

 

방의 개수 : 5

방의 최대 넓이 : 9

벽을 1개 부술때 최대 넓이 : 16

결과로 출력한다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 성곽에 대한 정보를 저장하였습니다.
• 성곽을 BFS탐색하여 방의 번호와 넓이를 구하는 bfs함수를 실행하였습니다.
• 각 방의 인접한 방끼리 넓이를 aroundSearch함수를 실행하였습니다.
• 방의 번호, 방의 최대 넓이, 벽을 1개 부순 방의 최대 넓이를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs는 성곽에 BFS탐색을 진행하여 각 방의 번호와 넓이를 구하는 함수입니다.
• aroundSearch은 해당 공간의 인접한 방 존재시 넓이의 합을 구하는 함수입니다.
• inCastle은 이동한 좌표가 성곽에 존재하는지 확인하는 함수입니다.
• wallCheck은 And(&)을 이용해서 해당 방향이 벽에 막혀있는지 확인하는 함수입니다.

 

import java.util.*;
import java.io.*;

public class Main {
	//성곽 위치 관련 클래스
    static class position{
        int x, y;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N,M;
    static int[][] castle;		//성곽 정보 저장하는 배열
    static int[][] roomId;		//방 번호 저장하는 배열
    static int[] dx = {-1, 0, 1, 0};	//서북동남 X변경값
    static int[] dy = {0, -1, 0, 1};	//서북동남 Y변경값
    static ArrayList<Integer> roomSize = new ArrayList<>();	//방 크기 저장하는 리스트
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        castle = new int[N][M];
        roomId = new int[N][M];
        //성곽에 대한 정보 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for (int j=0;j<M;j++){
                castle[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int roomIndex = 1;	//방 초기 번호: 1
        int maxSize = -1;	//방 최대 크기 초기화
        //1. 1. BFS 탐색으로 성곽에 존재하는 방들의 넓이와 번호를 부여합니다.
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(roomId[i][j]==0){
                    roomSize.add(bfs(j, i, roomIndex++));
                    maxSize = Math.max(maxSize,roomSize.get(roomSize.size()-1));
                }
            }
        }
        bw.write(--roomIndex + "\n");	//방의 개수 BufferedWriter 저장
        bw.write(maxSize + "\n");		//방의 최대 넓이 BufferedWriter 저장
        int doorBreakSize = -1;
        //2. 각 방에서 인접한 방에 넓이를 더한 최대값으로 벽을 1개 부술 때 최대 넓이를 구합니다.
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                doorBreakSize = Math.max(aroundSearch(j,i), doorBreakSize);
            }
        }
        bw.write(doorBreakSize + "");	//벽 1개 부순 방의 최대 넓이 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //성곽을 BFS탐색으로 방 번호와 방의 넓이를 구하는 함수
    static int bfs(int x, int y, int index){
        Queue<position> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        int count = 1;
        roomId[y][x] = index;
        visited[y][x] = true;
        queue.add(new position(x,y));
        while(!queue.isEmpty()){
            position cur = queue.poll();
            for(int i=0;i<4;i++){	//서북동남 이동하기
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                if(wallCheck(cur.x,cur.y,i) && !visited[tempY][tempX]){
                    count++;
                    roomId[tempY][tempX] = index;
                    visited[tempY][tempX] = true;
                    queue.add(new position(tempX,tempY));
                }
            }
        }
        return count;
    }
    //주변 인접한 방의 넓이를 더하는 함수
    static int aroundSearch(int x, int y){
        for(int i=0;i<4;i++){
            int tempX = x + dx[i];
            int tempY = y + dy[i];
            if(inCastle(tempX,tempY)){
                if(roomId[y][x] != roomId[tempY][tempX]){
                    return roomSize.get(roomId[y][x]-1) + roomSize.get(roomId[tempY][tempX]-1);
                }
            }
        }
        return -1;
    }
    //좌표가 성곽에 존재하는지 확인하는 함수
    static boolean inCastle(int x, int y){
        if(y>=0 && x>=0 && x<M && y<N)
            return true;
        return false;
    }
    //AND(&)를 이용하여 해당 방향에 벽이 존재하는지 확인하는 함수
    static boolean wallCheck(int x, int y, int index){
        if((castle[y][x] & (1<<index))==0)
            return true;
        return false;
    }
}