백준 5547 일루미네이션 c++ (bfs) 2022-07-06 Kotlin 추가

문제 출처 : https://www.acmicpc.net/problem/5547

5547번: 일루미네이션

문제

부유한 집안의 상속자 상근이네 집은 그림과 같이 1미터의 정육각형이 붙어있는 상태이다. 크리스마스가 다가오기 때문에, 여자친구에게 잘 보이기 위해 상근이는 건물의 벽면을 조명으로 장식하려고 한다. 외부에 보이지 않는 부분에 조명을 장식하는 것은 낭비라고 생각했기 때문에, 밖에서 보이는 부분만 장식하려고 한다.

위의 그림은 상공에서 본 상근이네 집의 건물 배치이다. 정육각형 안의 숫자는 좌표를 나타낸다. 여기서 회색 정육각형은 건물의 위치이고, 흰색은 건물이 없는 곳이다. 위에서 붉은 색 선으로 표시된 부분이 밖에서 보이는 벽이고, 이 벽에 조명을 장식할 것이다. 벽의 총 길이는 64미터이다.

상근이네 집의 건물 위치 지도가 주어졌을 때, 조명을 장식할 벽면의 길이의 합을 구하는 프로그램을 작성하시오. 지도의 바깥은 자유롭게 왕래 할 수 있는 곳이고, 인접한 건물 사이는 통과할 수 없다.

입력

첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 (j, i)이며, 건물이 있을 때는 1이고, 없을 때는 0이다. 주어지는 입력에는 건물이 적어도 하나 있다.

지도는 다음과 같은 규칙에 의해 만들어졌다.

• 지도의 가장 왼쪽 위에 있는 정육각형의 좌표는 (1,1)이다.
• (x,y)의 오른족에 있는 정육각형의 좌표는 (x+1,y)이다.
• y가 홀수 일 때, 아래쪽에 있는 정육각형의 좌표는 (x,y+1)이다.
• y가 짝수 일 때, 오른쪽 아래에 있는 정육각형의 좌표는 (x,y+1)이다.

출력

조명을 장식하는 벽면의 길이의 합을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

정육각형을 그래프로 다루긴 처음이라 당황했다.

 

회색으로 칠해진 부분이 건물이고, 흰색으로 칠해진 부분이 바깥이다.

바깥에서 보이는 부분만 조명을 장식하려면, 건물(회색)의 인접한 바깥(흰색)에서 맞닿는 면의 개수를

카운트해주면 된다.

 

즉, 흰색인 좌표(입력값이 0인 좌표)를 돌면서, 인접한 좌표가 흰색(입력값이 0인 좌표)이라면 계속 탐색,

인접한 좌표가 회색(입력값이 1인 좌표)이라면 조명의 개수를 추가, 이미 지나온 길은 탐색을 하지 않으면 된다.

 

해당 그래프의 탐색 방향은 정육각형의 인접한 칸이 6개이므로, 6방향으로 탐색을 할 수 있으며,

행(y좌표)이 짝수일 때, 홀수일 때 열(x좌표)의 값만 차이를 줘서 탐색한다.

 

주어진 행과 열이 4,8일 때,

주어진 입력을 벗어난 좌표도 바깥에 포함되기 때문에, 1행 1열에 건물이 있다면, 0행 1열도 탐색해야 하고,

4행 8열에 건물이 있다면 4행 9열도 탐색해야 하기 때문에, 그래프를 한 칸씩 더 여유롭게 만들자.

코드1(c++)

#include <iostream>
#include <queue>
using namespace std;
int graph[102][102];
int R, C;
//행이 짝수일 때
int even_dir[6][2] = { {1,-1},{1,0},{-1,-1},{-1,0},{0,-1},{0,1} };
//행이 홀수일 때
int odd_dir[6][2] = { {1,0},{1,1},{-1,0},{-1,1},{0,-1},{0,1} };
int bfs(int r, int c) {
	int result = 0;
	queue<pair<int, int>>q;
	q.push({ r, c });

	while (!q.empty()) {
		int curR = q.front().first;
		int curC = q.front().second;
		q.pop();
		//행이 짝수일 때
		if (curR % 2 == 0) {
			for (int i = 0; i < 6; i++) {
				int nextR = curR + even_dir[i][0];
				int nextC = curC + even_dir[i][1];
				if (nextR >= 0 && nextR <= R + 1 && nextC >= 0 && nextC <= C + 1) {
					if (graph[nextR][nextC] == 0) {
						q.push({ nextR,nextC });
						graph[nextR][nextC] = -1;//방문한 좌표는 -1로 표시
					}
					else if(graph[nextR][nextC]==1){
						result++;
					}
					
				}
			}
		}
		//행이 홀수일 때
		else {
			for (int i = 0; i < 6; i++) {
				int nextR = curR + odd_dir[i][0];
				int nextC = curC + odd_dir[i][1];
				if (nextR >= 0 && nextR <= R + 1 && nextC >= 0 && nextC <= C + 1) {
					if (graph[nextR][nextC] == 0) {
						q.push({ nextR,nextC });
						graph[nextR][nextC] = -1;//방문한 좌표는 -1로 표시
					}
					else if (graph[nextR][nextC] == 1) {
						result++;
					}
				}
			}
		}
	}


	return result;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> C >> R;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> graph[i][j];
		}
	}

	cout << bfs(0, 0);


	return 0;
}

코드2(Kotlin)

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

var answer = 0
lateinit var graph: Array<IntArray>
val dir = arrayOf(
    arrayOf(0, 1),
    arrayOf(0, -1),
    arrayOf(1, 0),
    arrayOf(-1, 0),
    //행이 홀수일 때
    arrayOf(-1, 1),
    arrayOf(1, 1),
    //행이 짝수일 때
    arrayOf(-1, -1),
    arrayOf(1, -1)
)

fun bfs(): Int {
    var sum = 0
    val q: Queue<Pair<Int,Int>> = LinkedList()
    q.add(Pair(0,0))
    while(q.isNotEmpty()) {
        val cur = q.poll()
        for (i in 0 until 8) {
            val nr = cur.first + dir[i][0]
            val nc = cur.second + dir[i][1]
            if (cur.first % 2 != 0 && i >= 6) continue
            if (cur.first % 2 == 0 && i in 4..5) continue
            if (nr !in graph.indices || nc !in graph[0].indices) continue
            if (graph[nr][nc] == 1) {
                sum++
            } else if (graph[nr][nc] == 0) {
                graph[nr][nc] = -1
                q.add(Pair(nr, nc))
            }
        }
    }
    return sum
}

fun main() = with(System.out.bufferedWriter()) {

    //input
    val (w, h) = getIntList()
    graph = Array(h+2) {IntArray(w+2)}
    for(r in 1 .. h){
        val input = getIntList()
        for(c in 1 .. w){
            graph[r][c] = input[c-1]
        }
    }

    //건물 외벽 훑기
    write("${bfs()}")

    close()
}