문제

어쩌다 보니 영어 문제를 또 풀게 되었다.

번역은 전문가를 초빙해 부탁드렸다.

InterGames는 인터넷을 통해 게임을 즐길 수 있는 기술을 개발하는 하이테크 스타트업 회사입니다. 시장 분석 결과, 잠재 고객들 사이에서 확률 게임이 매우 인기가 있다는 사실을 알게 되었습니다. 모노폴리, 루도, 백개먼과 같은 대부분의 게임들은 게임의 일부 단계에서 주사위를 던지는 과정을 포함하고 있습니다.

물론, 플레이어들이 주사위를 던지고 그 결과를 컴퓨터에 입력할 수 있도록 허용하는 것은 부당할 것입니다. 그렇게 하면 속임수가 너무 쉬워지기 때문입니다. 그래서 InterGames는 사용자가 던진 주사위를 촬영하여 이미지를 분석하고, 던진 결과를 자동으로 전송하는 카메라를 제공하기로 결정했습니다.

이를 위해, 주사위에 있는 점의 개수를 확인하는 프로그램이 절실히 필요합니다.

입력 이미지에 대해 다음과 같은 가정을 합니다. 이미지는 배경, 주사위, 주사위 위의 점이라는 세 가지 픽셀 값만 포함하고 있습니다. 두 픽셀이 동일한 가장자리를 공유하면 연결된 것으로 간주합니다. 코너에서 만나는 것은 연결로 간주하지 않습니다. 그림에서 픽셀 A와 B는 연결되어 있지만, B와 C는 연결되어 있지 않습니다.

픽셀의 집합 S는 S에 있는 모든 픽셀 쌍 (a, b)에 대해, S 내에 a1, a2, ..., ak라는 순서가 존재하며, a = a1이고 b = ak이며, 1 ≤ i < k에 대해 ai와 ai+1이 연결되어 있을 경우 연결된 것으로 간주됩니다.

배경 픽셀을 제외한 최대 연결 집합을 주사위로 간주합니다. '최대 연결'이란 다른 비배경 픽셀을 추가하면 연결되지 않게 되는 것을 의미합니다. 마찬가지로 점 픽셀의 최대 연결 집합을 점으로 간주합니다.

입력은 여러 주사위 던지기 사진으로 구성됩니다. 각 사진 설명은 두 개의 숫자 w와 h로 시작하는 줄로 이루어지며, 각각 사진의 너비와 높이를 나타냅니다. 이 값들은 5 ≤ w,h ≤ 50을 만족합니다.

다음의 h 줄에는 각각 w개의 문자들이 포함됩니다. 이 문자들은 다음과 같습니다:

"." : 배경 픽셀을 나타냅니다.
"*" : 주사위의 픽셀을 나타냅니다.
"X" : 주사위 위의 점의 픽셀을 나타냅니다.
주사위는 크기가 다를 수 있으며, 광학적 왜곡으로 인해 완전히 정사각형이 아닐 수도 있습니다. 사진에는 최소 하나의 주사위가 포함되며, 각 주사위의 점 개수는 1에서 6 사이입니다.

입력은 w = h = 0으로 시작하는 사진으로 종료되며, 이 사진은 처리하지 않아야 합니다.

각 주사위 던지기 사진에 대해, 먼저 그 사진의 번호를 출력합니다. 그런 다음, 사진에 있는 주사위에 표시된 점의 개수를 오름차순으로 정렬하여 출력합니다.

각 테스트 케이스(사진)의 출력이 끝난 후에는 빈 줄을 하나 출력합니다.

고마워요 지피티맨!

요약하자면 다음과 같다.

입력값으로는 주사위를 표현한 텍스트가 주어지며, 주사위의 눈은 X, 그 외의 주사위 표면은 *, 배경은 .으로 표현된다.

이 때 주사위는 인접한 픽셀로서 구성되는데, 한 변 이상이 맞닿은 픽셀은 인접했다고 인정된다. 그에 반해 꼭짓점만 맞닿은 픽셀은 인접했다고 보지 않는다.

마찬가지로 주사위의 눈 또한 인접한 픽셀로서 구성되는데, 조건은 주사위와 일치한다.

예를 들면 왼쪽의 주사위는 5개의 눈, 오른쪽의 주사위는 1개의 눈을 가졌다고 본다.

.....		.....
.x.x.		.xxx.
..x..		..x..
.x.x.		.xxx.
.....		.....

이처럼 주어진 입력값을 통해 주사위의 눈을 식별하고, 이를 오름차순으로 정렬하여 출력한다.

아이디어

인접한 점들을 식별하는 간단한 BFS 문제다.
다만 전체 이미지에서 BFS를 통해 주사위를 식별하고, 주사위 내에서 다시 BFS를 통해 주사위의 눈을 식별하는 이중 BFS가 필요하다.

나는 주사위를 식별하는 메서드와 주사위의 눈을 식별하는 메서드를 분리하였는데, 이 때 주사위 눈을 식별하는 과정에서 주사위의 눈이 아닌 부분을 인식했을 때, 처리하는 로직이 없어 고생했다.

이 부분만 신경쓴다면, (간단한 BFS) X 2의 문제.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int w;
    static int h;
    static Character[][] map;
    static Boolean[][] visited;
    static Queue<Integer> ans;
    static int[] dx = {0, 0, 1, 0, -1};
    static int[] dy = {0, 1, 0, -1, 0};

    static int idx = 0;
    static int temp;
    static Queue<Node> queue;

    static class Node {
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        int x;
        int y;
    }

    static void parseDot(int i, int j) {
        temp++;
        Queue<Node> dotQueue = new ArrayDeque<>();
        dotQueue.add(new Node(i, j));

        while (!dotQueue.isEmpty()) {
            Node curNode = dotQueue.poll();

            for (int k = 0; k < 5; k++) {
                int nextX = curNode.x + dx[k];
                int nextY = curNode.y + dy[k];

                if (nextX < 0 || nextX >= h || nextY < 0 || nextY >= w) continue;
                if (visited[nextX][nextY]) continue;
                if (!map[nextX][nextY].equals('X')) {
                    queue.add(new Node(nextX, nextY));
                    visited[nextX][nextY] = true;
                } else {
                    dotQueue.add(new Node(nextX, nextY));
                    visited[nextX][nextY] = true;
                }
            }
        }
    }

    static void parseDice(int i, int j) {
        temp = 0;
        queue = new ArrayDeque<>();
        queue.add(new Node(i, j));

        while (!queue.isEmpty()) {
            Node curNode = queue.poll();

            for (int k = 0; k < 5; k++) {
                int nextX = curNode.x + dx[k];
                int nextY = curNode.y + dy[k];

                if (nextX < 0 || nextX >= h || nextY < 0 || nextY >= w) continue;
                if (visited[nextX][nextY]) continue;
                if (map[nextX][nextY].equals('.')) continue;

                if (map[nextX][nextY].equals('X')) parseDot(nextX, nextY);

                queue.add(new Node(nextX, nextY));
                visited[nextX][nextY] = true;
            }
        }

        ans.add(temp);
    }

    static void parseImage() throws IOException {
        System.out.println("Throw " + idx);

        ans = new PriorityQueue<>();
        map = new Character[h][w];
        visited = new Boolean[h][w];
        for (int i = 0; i < h; i++) {
            Arrays.fill(visited[i], false);
        }

        for (int i = 0; i < h; i++) {
            String line = br.readLine();
            for (int j = 0; j < w; j++) {
                map[i][j] = line.charAt(j);
            }
        }


        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (visited[i][j]) continue;
                if (map[i][j].equals('.')) {
                    visited[i][j] = true;
                } else parseDice(i, j);
            }
        }

        while (!ans.isEmpty()) {
            System.out.print(ans.poll() + " ");
        }
        System.out.println();
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            if (w == 0 && h == 0) break;
            idx++;
            parseImage();
        }
    }
}

채점 결과

우선순위 큐에 정답을 저장하고 반복문으로 정답을 출력하는 귀여운 실수가 있었다.
그 외에는 상술한 점을 고려하지 못해 오답이었다.

맞춘 사람이 13명 밖에 되지 않는 문제여서 티어가 잘못되어있지 않을까 생각했지만, 나름 알맞은 티어였다고 생각된다.