BOJ) 성곽

성곽

2234번: 성곽

풀이

 

생각보다 코드가 길어진 문제다.

각 방에 대해 상하좌우에 벽이 있는지 없는지를 int형 숫자로 주어진다.

이 숫자는 각각 벽이 있다는 의미를 가진 2진수 숫자를 모두 더한 값이다.

 

벽의 방향	숫자
서	1
북	2
동	4
남	8

위의 벽 정보에 따라서 map의 숫자가 정해진다.

만약 서쪽과 북쪽에 벽이 있다면, 해당 방의 숫자는 3으로 주어지고, 동쪽과 남쪽은 12가 주어지는 식이었다.

그래서, 거추장스럽지만 0~15까지 움직일 수 있는 방향을 미리 저장했다. (어차피 0~15 사이의 숫자만 주어지기 때문)

 

1 : W, 2 : N, 4: E, 8 : S 불가능

주어진 숫자	E	W	S	N	이동 가능 방향
0	O	O	O	O	NEWS
1	O	X	O	O	ESN
2	O	O	O	X	EWS
3	O	X	O	X	ES
4	X	O	O	O	WSN
5	X	X	O	O	SN
6	X	O	O	X	WS
7	X	X	O	X	S
8	O	O	X	O	EWN
9	O	X	X	O	EN
10	O	O	X	X	EW
11	O	X	X	X	E
12	X	O	X	O	WN
13	X	X	X	O	N
14	X	O	X	X	W
15	X	X	X	X

총 16가지 경우의 수를 char[][]에 저장해주었다.

 

문제에서 요구한 출력은 총 세가지다

 

1. 이 성에 있는 방의 개수

2. 가장 넓은 방의 넓이

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

그래서 제일 먼저 한 일은 grouping을 해주는 것이다.

이상하게 grouping 문제를 한 번 풀고 나니까 grouping 문제가 많이 보인다... ㅎㅎ

각 좌표를 돌면서 group이 정해지지 않은 방에 대해서 BFS 탐색을 통해 group Index를 부여했다.

 

같은 group인 방은 하나의 방인 것이고, 서로 벽으로 막혀있으면 다른 방으로 간주한다.

동시에 index마다 grouping이 끝나면, 해당 index를 가진 방의 사이즈가 몇인지 HashMap에(roomSizeMap) 저장해주었다.

 

위의 과정을 끝내면 1번과 2번 출력을 구할 수 있다.

 

마지막 3번은, 모든 좌표를 돌면서 해당 방에 상하좌우를 탐색한다.

상하좌우에 다른 방 Index를 가진 방이 있으면, 벽으로 막혀있다는 소리다.

그런 방들에 대해 벽을 허물어서 두 방의 크기를 더한 값이 최대가 되는 크기를 구해주었다.

 

위의 과정을 거치면 1번 2번 3번 출력에 대한 정답을 구할 수 있다.

코드가 길지만, 어렵지만은 않은 문제다.

 

또한, 위의 로직에서 HashMap을 계속 호출하는 것이 효율성을 저해한다고 생각해서 각 방의 크기를 담은 int[][] 변수 sizeInfo를 만들어서, 각 인덱스에 해당하는 방의 크기를 저장해주었다. (단순히, HashMap 호출 수를 줄이기 위해서)

코드 2에 이 코드를 적어놨다.

결과적으로 시간과 메모리 효율이 더 좋았다.

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
    private final static char[][] moveArr= {{'N','E','W','S'},{'N','E','S'},{'E','W','S'},{'E','S'},{'S','W','N'},{'N','S'},{'W','S'},{'S'},{'E','W','N'},{'E','N'},{'E','W'},{'E'},{'W','N'},{'N'},{'W'},{}};
    private static HashMap<Character, CastlePos> direction;
    private static HashMap<Integer, Integer> roomSizeMap;
    static int maxRoom;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int[][] map = new int[n][m];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
        setDirection();
        solution(map,m,n);
    }

    private static void setDirection() {
        direction = new HashMap<>();
        direction.put('E', new CastlePos(1,0));
        direction.put('W', new CastlePos(-1, 0));
        direction.put('S', new CastlePos(0,1));
        direction.put('N', new CastlePos(0,-1));
    }

    private static void solution(int[][] map, int m, int n) {
        maxRoom =0;
        roomSizeMap = new HashMap<>();
        int breakWallRoomSize = 0;

        int[][] groupInfo = getGroups(map, m, n);

        int mul = m*n;
        for(int i=0; i<mul; i++) {
            int x = i%m;
            int y = i/m;
            int originGroup = groupInfo[y][x];

            for(int j=0; j<4; j++) {
                int nx = x+dx[j];
                int ny = y+dy[j];
                if(isInArea(nx,ny,m,n)) {
                    int targetGroup = groupInfo[ny][nx];
                    if(originGroup != targetGroup) {
                        int size = roomSizeMap.get(originGroup) + roomSizeMap.get(targetGroup);
                        breakWallRoomSize = Math.max(breakWallRoomSize, size);
                    }
                }
            }
        }

        System.out.println(roomSizeMap.size());  // 방의 갯수
        System.out.println(maxRoom); // 가장 넓은 방의 넓이
        System.out.println(breakWallRoomSize); // 벽을 하나 허물 경우 가장 넓은 방
    }

    private static int[][] getGroups(int[][] map, int m, int n) {
        int[][] groupInfo = new int[n][m];
        int idx =0;

        LinkedList<CastlePos> moveList = new LinkedList<>();
        int mul = m*n;
        for(int i=0; i<mul; i++) {
            int x = i%m;
            int y = i/m;
            if(groupInfo[y][x] ==0) {
                groupInfo[y][x] = ++idx;
                moveList.offer(new CastlePos(x,y));
                int cnt =1;

                while(!moveList.isEmpty()) {
                    CastlePos pos = moveList.poll();
                    for(char ch : moveArr[map[pos.y][pos.x]]) {
                        CastlePos directionPos = direction.get(ch);
                        int nx = pos.x + directionPos.x;
                        int ny = pos.y + directionPos.y;
                        if(groupInfo[ny][nx] ==0) {
                            cnt++;
                            groupInfo[ny][nx] = idx;
                            moveList.offer(new CastlePos(nx, ny));
                        }
                    }
                }
                maxRoom = Math.max(cnt,maxRoom);
                roomSizeMap.put(idx,cnt);
            }
        }
        return groupInfo;
    }

    private static boolean isInArea(int x, int y, int maxX, int maxY) {
        return x>=0 && x<maxX && y>=0 && y<maxY;
    }
}

class CastlePos {
    int x;
    int y;

    public CastlePos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

코드 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private final static int[] dx = {1,-1,0,0}, dy = {0,0,1,-1};
    private final static char[][] moveArr= {{'N','E','W','S'},{'N','E','S'},{'E','W','S'},{'E','S'},{'S','W','N'},{'N','S'},{'W','S'},{'S'},{'E','W','N'},{'E','N'},{'E','W'},{'E'},{'W','N'},{'N'},{'W'},{}};
    private static HashMap<Character, CastlePos> direction;
    private static HashMap<Integer, Integer> roomSizeMap;
    static int maxRoom, groupInfo[][], sizeInfo[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int[][] map = new int[n][m];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
        setDirection();
        solution(map,m,n);
    }

    private static void setDirection() {
        direction = new HashMap<>();
        direction.put('E', new CastlePos(1,0));
        direction.put('W', new CastlePos(-1, 0));
        direction.put('S', new CastlePos(0,1));
        direction.put('N', new CastlePos(0,-1));
    }

    private static void solution(int[][] map, int m, int n) {
        maxRoom =0;
        roomSizeMap = new HashMap<>();
        int breakWallRoomSize = 0;

        setInfos(map,m,n);

        int mul = m*n;
        for(int i=0; i<mul; i++) {
            int x = i%m;
            int y = i/m;
            int originGroup = groupInfo[y][x];

            for(int j=0; j<4; j++) {
                int nx = x+dx[j];
                int ny = y+dy[j];
                if(isInArea(nx,ny,m,n)) {
                    if(originGroup != groupInfo[ny][nx]) {
                        breakWallRoomSize = Math.max(breakWallRoomSize, sizeInfo[y][x]+sizeInfo[ny][nx]);
                    }
                }
            }
        }

        System.out.println(roomSizeMap.size());  // 방의 갯수
        System.out.println(maxRoom); // 가장 넓은 방의 넓이
        System.out.println(breakWallRoomSize); // 벽을 하나 허물 경우 가장 넓은 방
    }

    private static void setInfos(int[][] map, int m, int n) {
        groupInfo = new int[n][m];
        sizeInfo = new int[n][m];
        int idx =0;

        LinkedList<CastlePos> moveList = new LinkedList<>();
        int mul = m*n;
        for(int i=0; i<mul; i++) {
            int x = i%m;
            int y = i/m;
            if(groupInfo[y][x] ==0) {
                groupInfo[y][x] = ++idx;
                moveList.offer(new CastlePos(x,y));
                int cnt =1;

                while(!moveList.isEmpty()) {
                    CastlePos pos = moveList.poll();
                    for(char ch : moveArr[map[pos.y][pos.x]]) {
                        CastlePos directionPos = direction.get(ch);
                        int nx = pos.x + directionPos.x;
                        int ny = pos.y + directionPos.y;
                        if(groupInfo[ny][nx] ==0) {
                            cnt++;
                            groupInfo[ny][nx] = idx;
                            moveList.offer(new CastlePos(nx, ny));
                        }
                    }
                }
                maxRoom = Math.max(cnt,maxRoom);
                roomSizeMap.put(idx,cnt);
            }
            sizeInfo[y][x] = roomSizeMap.get(groupInfo[y][x]);
        }
    }

    private static boolean isInArea(int x, int y, int maxX, int maxY) {
        return x>=0 && x<maxX && y>=0 && y<maxY;
    }
}

class CastlePos {
    int x;
    int y;

    public CastlePos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}