백준 9518번 로마 카톨릭 미사 :: 마이구미

이 글은 백준 알고리즘 문제 9518번 "로마 카톨릭 미사" 를 풀이한다.

본인은 BFS를 응용하여 문제를 풀이하였다.

9518번 - https://www.acmicpc.net/problem/9518

BFS 이해 - http://mygumi.tistory.com/102

로마 카톨릭 미사에서 가장 멋진 부분은 사람들이 서로 악수를 하면서 "평화가 함께하기를" 이라고 말하는 평화 의식이다.

성당에는 R개의 벤치가 한 행에 하나씩 있고, 각 벤치에는 총 S명이 앉을 수 있다. 성당의 좌석 배치는 크기가 R × S인 행렬로 나타낼 수 있고, 행렬의 각 원소는 사람이 있는지 없는지로 나타낼 수 있다. 모든 사람은 자신의 이웃과 악수를 한다고 가정한다. 이웃은 사람이 있는 칸과 인접한 칸 여덟개이다. (칸이 존재하지 않을 수도 있다)

상근이는 오늘도 늦잠을 자 미사에 늦었고, 가장 좋아하는 평화 의식 시간을 참여하기 위해 성당 입구까지 달려왔다. 상근이는 최대한 많은 사람과 악수를 할 수 있는 자리에 앉으려고 한다. 만약, 남은 자리가 없는 경우에는 상근이는 저녁 미사에 다시 참가하려고 한다. 또, 상근이보다 지각하는 사람은 없다.

상근이가 들어가기 바로 전 성당에 앉아있는 사람의 배치가 주어진다. 평화 의식이 진행되는 동안 총 몇 번의 악수가 행해지는지 구하는 프로그램을 작성하시오.

주의할 점은, 문제에서 상근이가 가장 많이 악수하는 횟수를 구하는 것이 아닌, 그것을 포함한 모든 사람의 악수에 대한 총 횟수를 구한다.

본인은 상근이와 상근이 이외의 사람들의 악수를 분리하여 생각했다.

상근이가 악수할 수 있는 자리에서 가장 많은 악수를 하는 경우를 구한다.

이것은 단순한 방법으로 각 가능한 자리에서 할 수 있는 악수의 횟수를 구하면 된다.

그리고 상근이를 배치하기 전 주어진 사람들에 있어서, 할 수 있는 모든 악수의 횟수를 구하면 된다.

이 부분은 본인 같은 경우는 BFS를 응용하여 구현하였다.

그래프 알고리즘 문제 풀이 - 그래프 문제 카테고리

Github - https://github.com/hotehrud/acmicpc/tree/master/graph

static int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 };
static int[] dy = { 0, -1, -1, -1, 0, 1, 1, 1 };
static int r, s;
static char[][] array;
static boolean[][] visited;
static Queue<Point> q = new LinkedList<>();
 
private void solve() {
    r = sc.nextInt();
    s = sc.nextInt();
    array = new char[r][s];
    visited = new boolean[r][s];
    int ans = 0;
    for (int i = 0; i < r; i++) {
        array[i] = sc.next().toCharArray();
        for (int j = 0; j < s; j++) {
            if (array[i][j] == 'o') {
                q.add(new Point(i, j));
            }
        }
    }
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < s; j++) {
            int temp = 0;
            if (array[i][j] == '.') {
                for (int k = 0; k < 8; k++) {
                    int nx = dx[k] + j;
                    int ny = dy[k] + i;
 
                    if (0 <= nx && nx < s && 0 <= ny && ny < r) {
                        if (array[ny][nx] == 'o') {
                            ++temp;
                        }
                    }
                }
                if (ans < temp) {
                    ans = temp;
                }
            }
        }
    }
    System.out.println(maxHand() + bfs());
}
 
public static int maxHand() {
    int max = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < s; j++) {
            int temp = 0;
            if (array[i][j] == '.') {
                for (int k = 0; k < 8; k++) {
                    int nx = dx[k] + j;
                    int ny = dy[k] + i;
 
                    if (0 <= nx && nx < s && 0 <= ny && ny < r) {
                        if (array[ny][nx] == 'o') {
                            ++temp;
                        }
                    }
                }
                if (max < temp) {
                    max = temp;
                }
            }
        }
    }
    return max;
}
 
public static int bfs() {
    int size = q.size();
    int ans = 0;
 
    for (int i = 0; i < size; i++) {
        Point p = q.poll();
        visited[p.y][p.x] = true;
 
        for (int k = 0; k < 8; k++) {
            int nx = dx[k] + p.x;
            int ny = dy[k] + p.y;
 
            if (0 <= nx && nx < s && 0 <= ny && ny < r) {
                if (!visited[ny][nx] && array[ny][nx] == 'o') {
                    ++ans;
                }
            }
        }
    }
    return ans;
}
 
public static class Point {
    int x;
    int y;
 
    Point(int y, int x) {
        this.y = y;
        this.x = x;
    }
}