1. 문제 링크
https://www.acmicpc.net/problem/2234
2. 문제
요약
- 위 그림과 같이 생긴 성곽이 있는데, 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타냅니다.
- 성은 M x N개의 정사각형 칸으로 이루어접니다.
- 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있습니다.
- 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 문제입니다.
- 이 성에 있는 방의 개수
- 가장 넓은 방의 넓이
- 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
- 입력: 첫 번째 줄에 1보다 크거나 같고 50보다 작거나 같은 정수인 N, M이 주어지고 두 번째 줄부터 M개의 줄에 벽에 대한 정보가 주어집니다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1, 북쪽에 벽이 있을 때는 2, 동쪽에 벽이 있을 때는 4, 남쪽에 벽이 있을 때는 8을 더한 값이 주어집니다. 따라서 이 값은 0부터 15까지의 범위 안에 있습니다.
- 이진수의 각 비트를 생각하면 쉽습니다.
- 출력: 첫 번째 줄에 1의 답을, 두 번째 줄에 2의 답을, 세 번째 줄에 3의 답을 출력합니다.
3. 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, M;
static int[][] wallNum, roomNumber;
static Room[][] map;
static boolean[][] visited;
static HashSet<Integer>[] neighbor;
static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
static HashMap<Integer, Integer> nums;
static void input() {
Reader scanner = new Reader();
N = scanner.nextInt();
M = scanner.nextInt();
wallNum = new int[M][N];
map = new Room[M][N];
for(int row = 0; row < M; row++) {
for(int col = 0; col < N; col++) {
wallNum[row][col] = scanner.nextInt();
map[row][col] = new Room();
}
}
}
static void solution() {
makeMap();
int roomNum = 0;
visited = new boolean[M][N];
roomNumber = new int[M][N];
nums = new HashMap<>();
for(int row = 0; row < M; row++) {
for(int col = 0; col < N; col++) {
if(!visited[row][col]) {
roomNum++;
dfs(row, col, roomNum);
}
}
}
sb.append(roomNum).append('\n');
List<Map.Entry<Integer, Integer>> list = new ArrayList<>(nums.entrySet());
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> l1, Map.Entry<Integer, Integer> l2) {
return l2.getValue() - l1.getValue();
}
});
sb.append(list.get(0).getValue()).append('\n');
findNeighbor(roomNum);
sb.append(getMaxNum(roomNum));
System.out.println(sb);
}
static int getMaxNum(int roomNum) {
int answer = Integer.MIN_VALUE;
for(int room = 1; room <= roomNum; room++) {
for(int n : neighbor[room]) {
int sum = nums.get(room) + nums.get(n);
answer = Math.max(answer, sum);
}
}
return answer;
}
static void findNeighbor(int roomNum) {
neighbor = new HashSet[roomNum + 1];
for(int room = 1; room <= roomNum; room++) neighbor[room] = new HashSet<>();
for(int row = 0; row < M; row++) {
for(int col = 0; col < N; col++) {
int curRoom = roomNumber[row][col];
for(int dir = 0; dir < 4; dir++) {
int cx = row + dx[dir], cy = col + dy[dir];
if(isInMap(cx, cy)) {
if(roomNumber[cx][cy] != curRoom)
neighbor[curRoom].add(roomNumber[cx][cy]);
}
}
}
}
}
static void makeMap() {
for(int row = 0; row < M; row++) {
for(int col = 0; col < N; col++) {
int wall = wallNum[row][col];
for(int num = 8; num > 0; num /= 2) {
if(wall < num) continue;
wall -= num;
if(num == 8) map[row][col].south = true;
else if(num == 4) map[row][col].east = true;
else if(num == 2) map[row][col].north = true;
else if(num == 1) map[row][col].west = true;
}
}
}
}
static void dfs(int x, int y, int roomNum) {
visited[x][y] = true;
roomNumber[x][y] = roomNum;
nums.put(roomNum, nums.getOrDefault(roomNum, 0) + 1);
for(int dir = 0; dir < 4; dir++) {
int cx = x + dx[dir], cy = y + dy[dir];
if(isInMap(cx, cy)) {
if(dir == 0) {
if(map[x][y].north) continue;
} else if(dir == 1) {
if(map[x][y].west) continue;
} else if(dir == 2) {
if(map[x][y].south) continue;
} else {
if(map[x][y].east) continue;
}
if(!visited[cx][cy]) {
dfs(cx, cy, roomNum);
}
}
}
}
static boolean isInMap(int x, int y) {
if(x >= 0 && x < M && y >= 0 && y < N) return true;
return false;
}
static class Room {
boolean west, north, east, south;
public Room() {
this.west = false;
this.north = false;
this.east = false;
this.south = false;
}
public Room(boolean west, boolean north, boolean east, boolean south) {
this.west = west;
this.north = north;
this.east = east;
this.south = south;
}
}
public static void main(String[] args) {
input();
solution();
}
static class Reader {
BufferedReader br;
StringTokenizer st;
public Reader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while(st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}4. 접근
- 각 칸의 동서남북에 벽이 있는지를 멤버로 가지는 Room이라는 클래스를 생성합니다.
- Room 타입의 2차원 배열인 map을 만들고 입력받은 성의 지도를 이용하여 각 칸의 동서남북에 벽이 있는지 계산하여 나타냅니다.
- 비트마스킹으로 진행할 수도 있지만 여기서 저는 8, 4, 2, 1 이렇게 빼나가는 과정으로 풀이하였습니다.
- 각 칸의 벽에 대한 정보를 이용하여 해당 정보에서 8, 4, 2, 1 순으로 빼나갑니다.
- 예를 들어, 벽에 대한 정보를 나타내는 수가 7이라면, 우선 8과 비교하여 8보다 큰지 확인하고 8보다 작기 때문에 남쪽에는 벽이 없다는 뜻이므로 빼지 않고 넘어가고, 이후에 4와 비교하여 4보다 큰지 확인하고 4보다 크기 때문에 동쪽에 벽이 있다는 뜻이므로 해당 위치의 Room 객체의 east 값을 true로 변경하고 4를 뺍니다.
- 이러한 방식으로 1까지 진행합니다.
- 이렇게 지도를 완성하고 모든 칸들을 방문하여 DFS를 통해 방의 개수와 가장 넓은 방의 넓이, 각 칸의 방의 번호를 구합니다.
- 방의 개수를 나타내는 roomNum, 각 칸의 방의 번호를 나타내는 2차원 배열 roomNumber와 각 칸을 방문했는지 여부를 나타내는 2차원 배열 visited, 각 방이 몇 개의 칸으로 이루어졌는지를 나타내는 HashMap nums를 생성합니다.
- 각 칸을 돌면서 아직 방문하지 않은 칸이라면 roomNum을 1 증가시키고 DFS를 통해 인접한 칸들 중 아직 방문하지 않은 칸들을 방문하여 각 칸의 방의 번호와 해당 방에서의 칸의 개수, 각 칸의 방문 체크를 진행합니다.
- 위 DFS 과정을 통해 roomNum을 이용하여 1번의 답을 구할 수 있습니다.
- nums를 칸의 개수를 기준으로 내림차순으로 정렬한 후에 가장 앞에 있는 방의 칸의 개수를 이용하여 2번의 답을 구합니다.
- 각 방의 주변 방들을 구합니다.
- HashSet 배열 neighbor를 생성하고 각 칸을 돌며 각 방과 인접한 방을 neighbor에 넣어 각 방에 인접한 방들을 찾습니다.
- 각 방에 인접한 방들을 구했기 때문에 인접한 두 방을 보고 그 두 방의 칸의 개수를 더합니다.
- 모든 경우에 대해 두 방의 칸의 개수의 합을 구하고 그 중 가장 큰 값이 3번의 답이 됩니다.
자바, 웹 개발을 열심히 공부하고 있습니다!