글 읽기 - 12946 java 반례를 모르겠습니다 ㅠㅠㅠ

2weeks0 1년 전 0

TC랑 질문 글에 있는 반례는 다 성공했는데, 뭐가 문제인지 잘 모르겠네요..

로직을 설명드리면 아래와 같습니다.

최대 3가지 색을 사용하면 되므로 색을 1,2,3으로 칭하겠습니다.

DFS를 굳이 안해도 될 것 같다고 판단했고, 2중 for문으로 완탐을 돌렸습니다.

인접한 칸에서 1,2,3 중 사용하지 않은 낮은 숫자를 사용합니다.

0, 1, 3가지 색을 사용해야만 하는 경우는 다 맞을 것 같고, 2가지 색을 사용할 경우에서 틀린 것 같은데, 도무지 반례를 생각해낼 수가 없네요ㅠ

도와주시면 감사드리겠습니다!!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static final int[] dr = {-1, -1, 0, 1, 1, 0};
    static final int[] dc = {0, 1, 1, 0, -1, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] board = new int[n][n];
        for (int r = 0; r < n; r++) {
            String line = br.readLine();
            for (int c = 0; c < n; c++) {
                board[r][c] = line.charAt(c) == 'X' ? 0 : -1;
            }
        }

        Set<Integer> set = new HashSet<>();
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] != 0) {
                    continue;
                }

                int[] visited = new int[4];
                for (int d = 0; d < dr.length; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr < 0 || n <= nr || nc < 0 || n <= nc || board[nr][nc] < 1) {
                        continue;
                    }

                    visited[board[nr][nc]]++;
                }

                for (int i = 1; i < 4; i++) {
                    if (visited[i] == 0) {
                        board[r][c] = i;
                        set.add(i);
                        break;
                    }
                }
            }
        }

        System.out.println(set.size());
        br.close();
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

12946 java 반례를 모르겠습니다 ㅠㅠㅠ

2weeks0 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말