백준 5547 - 일루미네이션
Updated:
Java
5547 번 - 일루미네이션
문제
접근 방법
코드가 길고 복잡하다.
각 건물의 벽 개수를 모두 센 뒤, 건물로 둘러쌓인 내벽의 개수를 빼줘 해결하였다.
문제는 내벽의 개수를 세는 것인데, 빈 공간이 바깥과 이어져 있는지 확인하는 과정이 번거로웠다.
이어져 있는 공간끼리 하나의 인덱스 부여 하여 모든 빈공간을 그룹화 한 뒤,
그룹화된 공간이 바깥과 이어져 있으면 해당 인덱스의 그룹은 바깥과 이어져 있다는 표시를 하였다.
이 절차 이후 그룹화된 공간 중 내벽의 공간만 구별이 되는데, 해당 공간의 외벽의 수를 앞서 구한 전체 외벽의 수에 빼준다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m, result;
static int[][] map;
static int[][] idxMap;
static boolean[][] vis;
static List<Boolean> isInList = new ArrayList<Boolean>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
m = stoi(stk.nextToken());
n = stoi(stk.nextToken());
map = new int[n][m];
idxMap = new int[n][m];
vis = new boolean[n][m];
for(int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
for(int j = 0; j < m; j++) {
map[i][j] = stoi(stk.nextToken());
}
}
// 건물의 모든 경계선의 개수를 센다
int odd[][] = new int[2][6];
odd[0] = new int[] {-1,-1,0,1,1,0};
odd[1] = new int[] {-1,0,1,0,-1,-1};
int even[][] = new int[2][6];
even[0] = new int[] {-1,-1,0,1,1,0};
even[1] = new int[] {0,1,1,1,0,-1};
for(int y = 0; y < n; y++) {
for(int x = 0; x < m; x++) {
if(map[y][x] == 0)
continue;
if(y % 2 == 0) {
calRst(y,x, even);
}else {
calRst(y,x, odd);
}
}
}
//System.out.println(result); // 건물 겉부분의 개수만 센 상태
// 건물이 없는 곳들을 그룹화 한다.
isInList.add(false);
putIdxMap(odd, even);
for(int[] temp : idxMap) {
// System.out.println(Arrays.toString(temp));
}
int idx;
// 그룹화 한 빈공간이 밖과 이어져 있는지 확인
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(map[i][j] == 1)
continue;
if(i == 0 || j == 0 || i == n - 1 || j == m - 1) {
isInList.set(idxMap[i][j], false);
}
}
}
//System.out.println(isInList);
// 건물 내부에 있는 빈 공간의 벽면 개수를 제거한다.
for(int y = 0; y < n; y++) {
for(int x = 0; x < m; x++) {
if(map[y][x] == 1 || !isInList.get(idxMap[y][x]))
continue;
if(y % 2 == 0) {
minusRst(y,x, even);
}else {
minusRst(y,x, odd);
}
}
}
System.out.println(result);
br.close();
}
// 건물 외벽의 수를 센다
static void calRst(int y, int x, int[][] dir) {
int ny, nx;
for(int i = 0; i < 6; i++) {
ny = y + dir[0][i];
nx = x + dir[1][i];
// 범위 밖은 나갔을 때 : 장식할 벽면
if(!isIn(ny,nx)) {
result++;
}
else {
// 빈putIdxMap공간과 건물이 붙어 있을 때 : 장식할 벽면
if(map[y][x] != map[ny][nx])
result++;
}
}
}
// 건물 외벽의 수를 센다
static void minusRst(int y, int x, int[][] dir) {
int ny, nx;
for(int i = 0; i < 6; i++) {
ny = y + dir[0][i];
nx = x + dir[1][i];
// 범위 밖은 나갔을 때 : 장식할 벽면
if(isIn(ny,nx) && map[ny][nx] == 1)
result--;
}
}
// 건물 외벽의 개수
static int idx;
private static void putIdxMap(int[][] odd, int[][] even) {
int[] curN;
idx = 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
// 방문하지 않았으며, 건물이 없는 곳이면
if(!vis[i][j] && map[i][j] == 0) {
curN = new int[] {i,j};
DFS(curN, odd, even);
idx++;
isInList.add(true);
}
}
}
}
// DFS로 번호 부여
private static void DFS(int[] curN, int[][] odd, int[][] even) {
int y = curN[0];
int x = curN[1];
int ny,nx;
// 한번 방문한 곳이면 리턴
if(vis[y][x])
return;
// 인덱스 부여
idxMap[y][x] = idx;
vis[y][x] = true;
if(y % 2 == 0) {
for(int i = 0; i < 6; i++) {
ny = y + even[0][i];
nx = x + even[1][i];
if(isIn(ny,nx) && !vis[ny][nx] && map[ny][nx] == 0) {
DFS(new int[] {ny,nx}, odd, even);
}
}
}else {
for(int i = 0; i < 6; i++) {
ny = y + odd[0][i];
nx = x + odd[1][i];
if(isIn(ny,nx) && !vis[ny][nx] && map[ny][nx] == 0) {
DFS(new int[] {ny,nx}, odd, even);
}
}
}
}
static int stoi(String str) {
return Integer.parseInt(str);
}
static boolean isIn(int y, int x) {
if(0 <= y && y < n && 0 <= x && x < m)
return true;
return false;
}
}
