백준 - 2578번(빙고)

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

---

문제

• 빙고 게임은 다음과 같은 방식으로 이루어진다.

• 먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다

• 다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5, 10, 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다.

• 차례로 수를 지워가다가 같은 가로줄, 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다.

• 이러한 선이 세 개 이상 그어지는 순간 "빙고"라고 외치는데, 가장 먼저 외치는 사람이 게임의 승자가 된다.

• 철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때, 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지를 출력하는 프로그램을 작성하시오.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static boolean leftToRight = false;
    private static boolean rightToLeft = false;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int[][] bingo = new int[5][5];
        int bingoCount = 0;
        int result = 0;

        for (int i = 0; i < 5; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < 5; j++) {
                bingo[i][j] = Integer.parseInt(tokenizer.nextToken());
            }
        }

        Outer: for (int i = 0; i < 5; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < 5; j++) {
                bingoCount += findBingo(bingo, Integer.parseInt(tokenizer.nextToken()));

                if (bingoCount >= 3) {
                    result = i * 5 + (j + 1);
                    break Outer;
                }
            }
        }

        System.out.println(result);
    }

    private static int findBingo(int[][] bingo, int answer) {
        int targetX = 0; // 찾을 행
        int targetY = 0; // 찾을 열

        int bingoCount = 0;

        // 대상 찾기
        Outer: for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (bingo[i][j] == answer) {
                    targetX = i;
                    targetY = j;
                    bingo[i][j] = 0;
                    break Outer;
                }
            }
        }

        // 찾았다면은, 빙고를 체크할 차례
        // 좌, 우 살피고 상, 하 살피고 대각은 제일 마지막

        // 좌, 우, 상, 하, 대각
        int[][] directions = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
        int directionIndex = 0; // 배열 인덱스

        int tempX = targetX;
        int tempY = targetY;
        int temp = 0; // 0 갯수 세기

        // 좌, 우
        while (directionIndex < 2) {
            int dx = tempX + directions[directionIndex][0];
            int dy = tempY + directions[directionIndex][1];

            if (dx >= 0&& dx < 5 && dy >= 0 && dy < 5) {
                // 0일 경우 계속 탐색
                if (bingo[dx][dy] == 0) {
                    temp++;
                    tempX = dx;
                    tempY = dy;
                    continue;
                } else {
                    break;
                }
            } else {
                tempX = targetX;
                tempY = targetY;
                directionIndex++;
            }
        }

        if (temp == 4) bingoCount++;

        tempX = targetX;
        tempY = targetY;
        temp = 0;

        directionIndex = 2;

        // 상, 하
        while (directionIndex < 4) {
            int dx = tempX + directions[directionIndex][0];
            int dy = tempY + directions[directionIndex][1];

            if (dx >= 0&& dx < 5 && dy >= 0 && dy < 5) {
                // 0일 경우 계속 탐색
                if (bingo[dx][dy] == 0) {
                    temp++;
                    tempX = dx;
                    tempY = dy;
                    continue;
                } else {
                    break;
                }
            } else {
                tempX = targetX;
                tempY = targetY;
                directionIndex++;
            }
        }

        if (temp == 4) bingoCount++;

        temp = 0;

        // 대각
        if (!leftToRight) {
            for (int i = 0; i < 5; i++) {
                if (bingo[i][i] == 0) {
                    temp++;
                } else {
                    break;
                }
            }

            if (temp == 5) {
                bingoCount++;
                leftToRight = true;
            }
        }

        temp = 0;

        // 대각
        if (!rightToLeft) {
            for (int i = 0; i < 5; i++) {
                if (bingo[i][4 - i] == 0) {
                    temp++;
                } else {
                    break;
                }
            }

            if (temp == 5) {
                bingoCount++;
                rightToLeft = true;
            }
        }


        return bingoCount;
    }

}

---

• 간단한 문제로 생각하고 접근하였으나 구현에 꽤 오랜 시간이 소요됐다.
• 먼저 2차원 배열에 대상 숫자를 저장한다.
• 사회자가 숫자 하나를 불러줄 때마다 연산을 수행하며, 빙고의 갯수가 3 이상이 되면 종료한다. 이때, "3 이상"이 중요하다. 처음에 3이 될 때 종료되는 조건으로 하였다가 문제를 실패하였다. 하나의 숫자가 채워짐으로서 2개의 빙고가 완성될 수도 있기 때문에 3 이상으로 처리하는 것이 바람직하다.
• 숫자 하나가 들어오면 먼저 대상의 인덱스를 구한다. 대상 숫자는 0으로 바꾼다.
• 인덱스를 찾았으면, 좌, 우, 상, 하 4방향 탐색을 시작한다. 좌와 우, 상과 하 2번에 나누어 탐색하며, 이동한 곳의 값이 0일 경우 해당 방향으로 계속 진행한다. 0이 아니면 그 라인에는 빙고가 없으므로 반복을 종료한다.
• 대각선은 2가지 경우가 존재하므로 마지막 탐색에서 2가지 대각선을 살핀다. 이때, 한번 처리한 대각선을 또 카운팅하여 에러가 뜨는 문제가 있었다. boolean 값으로 flag를 줘서 해결하였다.