[JAVA][백준 1730] 판화

https://www.acmicpc.net/problem/1730

 

오늘부터 문제는 올리지 않기로 했다!

---

풀이

처음에는 단순한 시뮬레이션 문제인 줄 알았는데 생각보다 복잡했다...

처음 풀이는 현재 좌표에만 무늬를 새겨넣고 다음에 갈 곳엔 새기지 않았는데 그렇게 했더니 마지막 위치에 마지막 명령을 시행하지 않는 문제가 생겼다

↓ 이전 풀이 방법 ↓

package S_1730;
// 판화

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

public class Main {
    private static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static char[] dc = {'U', 'D', 'L', 'R'};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        char[][] board = new char[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j] = '.';
            }
        }
        String command = br.readLine();

        int r = 0;
        int c = 0;
        char prevCM = '.';

        board: for (int i = 0; i < command.length(); i++) {
            char cm = command.toCharArray()[i];
            int nr = r;
            int nc = c;
            int cmNum = 0;

            // 다음 지표
            for (int j = 0; j < 4; j++) {
                if (cm == dc[j]) {
                    nr = r + d[j][0];
                    nc = c + d[j][1];
                    // 다음 지표가 격자를 벗어난다면 명령 무시
                    if (nr < 0 || nc < 0 || nr >= N || nc >= N) {
                        continue board;
                    }
                    cmNum = j;
                    break;
                }
            }

            if (i == 0) {
                if (cmNum <= 1){
                    board[r][c] = '|';
                    prevCM = '|';
                } else {
                    board[r][c] = '-';
                    prevCM = '-';
                }
            }

            if (cmNum <= 1) {  // 세로
                if (prevCM == '|') {
                    board[r][c] = '|';
                } else {
                    board[r][c] = '+';
                    prevCM = '|';
                }
            } else {    // 가로
                if (prevCM == '|') {
                    board[r][c] = '+';
                    prevCM = '-';
                } else {
                    board[r][c] = '-';
                }
            }

            r = nr;
            c = nc;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }

    }
}

 

 

그래서 방법을 한턴에서 다음 가야할 곳의 위치까지 그려넣는 방법으로 푸는 것으로 바꾸었다.

다 풀고 테스트케이스는 통과하여 제출했는데 실패...
틀렸다고 나온다..

package S_1730;
// 판화

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

public class Main {
    private static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static char[] dc = {'U', 'D', 'L', 'R'};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        char[][] board = new char[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j] = '.';
            }
        }
        String command = br.readLine();

        int r = 0;
        int c = 0;

        board: for (int i = 0; i < command.length(); i++) {
            char cm = command.toCharArray()[i];
            char shape = '.';
            int nr = r;
            int nc = c;

            for (int j = 0; j < 4; j++) {
                if (cm == dc[j]) {
                    nr += d[j][0];
                    nc += d[j][1];

                    // 범위를 벗어났다면 무시하고 다음 명령 수행
                    if (nr < 0 || nc < 0 || nr >= N || nc >= N){
                        continue board;
                    }

                    if (j <= 1) {
                        shape = '|';
                    } else {
                        shape = '-';
                    }

                    break;
                }
            }

            // 현재 자리 확인하고 현재 그려야하는 선이 이전에 그린 선과 모양이 다를때만 +로 표시
            if (board[r][c] == '.') {
                board[r][c] = shape;
            } else {
                if (board[r][c] != shape) {
                    board[r][c] = '+';
                }
            }
            board[nr][nc] = shape;

            r = nr;
            c = nc;

        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }
}

도저히 반례를 못찾겠어서 질문게시판을 뒤졌는데
새로 기록하는 부분을 그냥 바로 입력해야하는 모양을 그대로 입력하고 지나갔는데,

과거에 해당 부분을 바꿨었다면 그 기록을 토대로 교차하는지 아닌지 확인을 해줘야된다는 것이다.

그래서 코드를 아래처럼 바꾸었다

// 이전코드 : 현재 자리 확인하고 현재 그려야하는 선이 이전에 그린 선과 모양이 다를때만 +로 표시
            if (board[r][c] == '.') {
                board[r][c] = shape;
            } else {
                if (board[r][c] != shape) {
                    board[r][c] = '+';
                }
            }
            board[nr][nc] = shape;


// 바뀐 코드 : 
// 현재 자리 확인하고 현재 그려야하는 선이 이전에 그린 선과 모양이 다를때만 +로 표시
            draw(r, c, shape);
            draw(nr, nc, shape);

private static void draw(int r, int c, char shape) {
        if (board[r][c] == '.') {
            board[r][c] = shape;
        } else {
            if (board[r][c] != shape) {
                board[r][c] = '+';
            }
        }
    }

일단은 성공...!! 다들 반례를 어떻게 생각해내는 걸까..?ㅜㅜ

package S_1730;
// 판화

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

public class Main {
    private static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static char[] dc = {'U', 'D', 'L', 'R'};
    private static char[][] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        board = new char[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j] = '.';
            }
        }
        String command = br.readLine();

        int r = 0;
        int c = 0;

        board: for (int i = 0; i < command.length(); i++) {
            char cm = command.toCharArray()[i];
            char shape = '.';
            int nr = r;
            int nc = c;

            for (int j = 0; j < 4; j++) {
                if (cm == dc[j]) {
                    nr += d[j][0];
                    nc += d[j][1];

                    // 범위를 벗어났다면 무시하고 다음 명령 수행
                    if (nr < 0 || nc < 0 || nr >= N || nc >= N){
                        continue board;
                    }

                    if (j <= 1) {
                        shape = '|';
                    } else {
                        shape = '-';
                    }

                    break;
                }
            }

            // 현재 자리 확인하고 현재 그려야하는 선이 이전에 그린 선과 모양이 다를때만 +로 표시
            draw(r, c, shape);
            draw(nr, nc, shape);

            r = nr;
            c = nc;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }

    private static void draw(int r, int c, char shape) {
        if (board[r][c] == '.') {
            board[r][c] = shape;
        } else {
            if (board[r][c] != shape) {
                board[r][c] = '+';
            }
        }
    }
}