GOSE_KOSE

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 - 감시 자바 풀이를 진행하고자 합니다.

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

1. 풀이 소스:

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        Cctv cctv = new Cctv(n, m); // 인스턴스 생성
        
        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++)
                cctv.setMap(row, col, parseInt(st.nextToken()));
        }
        
        cctv.build();
        
        System.out.println(cctv.getMinNonSafeRegion());
    }
}

class Cctv {
    
    static final int[] DR = {-1, 0, 1, 0, -1, 0}; // -1, 0, 1, 0 에 추가로 -1, 0 을 넣은 이유 참조 #1
    static final int[] DC = {0, -1, 0, 1, 0, -1};
    
    int n; // row 총 개수
    int m; // col 총 개수
    int safeCnt; // 벽과 cctv 개수를 포함한 개수
    int maxSafeCnt; // 최고 안전 지대 개수
    int[][] map;
    List<Point> cctvs = new ArrayList<>(); // cctv를 저장할 리스트
    
    Cctv (int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m];
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
        
        if (value != 0) safeCnt++; // 만약 cctv 혹은 벽이라면 안전지대 개수 추가
        if (value != 0 && value != 6) cctvs.add(new Point(row, col)); // cctv 추가
    }
    
    void build() {
        if (cctvs.isEmpty()) { // cctv가 없을 수 있으므로 safeCnt 바로 maxSafeCnt로 할당하고 종료
            maxSafeCnt = safeCnt;
            return;
        }

        boolean[][] nowVisited = new boolean[n][m]; // 방문 위치 설정
        int nowSafeCnt = safeCnt; // nowSafeCnt로 지역변수 설정 후 재귀
        dfs(0, nowSafeCnt, nowVisited);
    }

    // idx: cctv 리스트를 순회할 인덱스, preSafeCnt: 이전 재귀에서 얻은 안전지대 개수, preVisited: 이전 재귀에서 방문한 곳
    void dfs(int idx, int preSafeCnt, boolean[][] preVisited) {
        if (idx == cctvs.size()) { // 만약 모든 cctv를 전부 탐색했다면
            maxSafeCnt = Math.max(preSafeCnt, maxSafeCnt);
            return; // 최대값 업데이트 후 종료
        }
        Point p = cctvs.get(idx); // 인덱스로 cctv 포인트 가져오기
        int row = p.row;
        int col = p.col;
        int value = map[row][col];

        if (value == 1) { // 1번 시시티비라면
            for (int k = 0; k < 4; k++) { // 상 하 좌 우 한 번만 이동 가능
                int nowSafeCnt = preSafeCnt; // nowSafeCnt로 지역 변수 할당 참조#2
                boolean[][] nowVisited = getNowVisited(preVisited); // preVisted를 깊은 복사한 nowVisited 생성
                nowSafeCnt = viewToDir(row, col, DR[k], DC[k], nowSafeCnt, nowVisited); // while문으로 벽이 나올 때까지 탐색 참조#3
                dfs(idx + 1, nowSafeCnt, nowVisited); // 재귀 실행
            }
        }

        else if (value == 2) {
            for (int k = 0; k < 2; k++) { // 짝 i = 0, i = 2 // i = 1, i = 3
                int nowSafeCnt = preSafeCnt;
                boolean[][] nowVisited = getNowVisited(preVisited);
                for (int d = 0; d < 2; d++) // 2번은 '좌우' 혹은 '상하'가 짝이므로 이중 포문으로 짝이 나올 수 있도록 2d + k 설정
                    nowSafeCnt = viewToDir(row, col, DR[k + 2 * d], DC[k + 2 * d], nowSafeCnt, nowVisited);
                dfs(idx + 1, nowSafeCnt, nowVisited);
            }
        }

        else if (value == 3) {
            for (int k = 0; k < 4; k++) {
                int nowSafeCnt = preSafeCnt;
                boolean[][] nowVisited = getNowVisited(preVisited);
                for (int d = 0; d < 2; d++) // 3번은 'ㄱ' 이 나와야 하므로 k + d로 '상좌', '좌하', '하우', '우상' 설정
                    nowSafeCnt = viewToDir(row, col, DR[k + d], DC[k + d], nowSafeCnt, nowVisited);
                dfs(idx + 1, nowSafeCnt, nowVisited);
            }
        }

        else if (value == 4) {
            for (int k = 0; k < 4; k++) {
                int nowSafeCnt = preSafeCnt;
                boolean[][] nowVisited = getNowVisited(preVisited);
                for (int d = 0; d < 3; d++) // 4번은 'ㅜ'가 나와야 하므로 k + d로  '상하좌', '상하우', '좌우상' '좌우하' 설정
                    nowSafeCnt = viewToDir(row, col, DR[k + d], DC[k + d], nowSafeCnt, nowVisited);
                dfs(idx + 1, nowSafeCnt, nowVisited);
            }
        }

        else {
            int nowSafeCnt = preSafeCnt;
            boolean[][] nowVisited = getNowVisited(preVisited);
            for (int k = 0; k < 4; k++) // 5번은 상하좌우 모두 탐색해야하므로 단일 포문으로 모두 탐색하도록 진행
                nowSafeCnt = viewToDir(row, col, DR[k], DC[k], nowSafeCnt, nowVisited);
            dfs(idx + 1, nowSafeCnt, nowVisited);
        }
    }

    // 유효한 인덱스에 row, col의 map 값이 벽이 아니여야함 (cctv는 통과 가능)
    boolean isValid(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < m && map[row][col] != 6;
    }

    int viewToDir(int row, int col, int dr, int dc, int nowSafeCnt, boolean[][] nowVisited) {
        while(true) {
            row += dr; // row에 값 업데이트
            col += dc; // col에 값 업데이트

            if (!isValid(row, col)) break; // 만약 벽이거나 유효한 인덱스가 아니라면 종료
            if (!nowVisited[row][col] && map[row][col] == 0) { // 방문하지 않은 경우에만
                nowVisited[row][col] = true;
                nowSafeCnt++;
            }
        }
        return nowSafeCnt;
    }

    boolean[][] getNowVisited(boolean[][] preVisited) { // 깊은 복사 진행
        boolean[][] nowVisited = new boolean[n][m];
        for (int r = 0; r < n; r++) nowVisited[r] = preVisited[r].clone();
        return nowVisited;
    }
    
    int getMinNonSafeRegion() {
        return n * m - maxSafeCnt;
    }
        
    static class Point {
        int row;
        int col;
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

2. 풀이 중점 사항

해당 문제는 정답률을 보았을 때, 쉬운 문제처럼 느껴질 수 있었지만 굉장히 복잡하고 실수를 유발하는 문제였습니다.

문제 자체는 이해가 빠르게 되었지만 이걸 어떻게 구현해야 할까라는 고민을 많이 하였습니다. 코드를 작성하는 과정에도 "잘못 풀고 있나?"라는 생각을 하면서 해결했던 것 같습니다.

먼저 이 문제는 5가지의 cctv를 다른 방법으로 탐색시켜야 했습니다. 따라서, DR, DC를 -1, 0, 1, 0 으로 설정하지 않고 다르게 설정하였습니다.

참조#1

static final int[] DR = {-1, 0, 1, 0, -1, 0}; // -1, 0, 1, 0 에 추가로 -1, 0 을 넣은 이유 참조 #1
static final int[] DC = {0, -1, 0, 1, 0, -1};

DR, DC를 다음과 같이 6개의 값으로 초기화 한 이유는  아래의 예시처럼 각각 다른 CCTV가 보이는 방향을 하나의 static final 배열의 DR, DC로 설정하기 위함입니다.

if (value == 1) { // 1번 시시티비라면
    for (int k = 0; k < 4; k++) { // 상 하 좌 우 한 번만 이동 가능
        int nowSafeCnt = preSafeCnt; // nowSafeCnt로 지역 변수 할당 참조#2
        boolean[][] nowVisited = getNowVisited(preVisited); // preVisted를 깊은 복사한 nowVisited 생성
        nowSafeCnt = viewToDir(row, col, DR[k], DC[k], nowSafeCnt, nowVisited); // while문으로 벽이 나올 때까지 탐색 참조#3
        dfs(idx + 1, nowSafeCnt, nowVisited); // 재귀 실행
    }
}

else if (value == 2) {
    for (int k = 0; k < 2; k++) { // 짝 i = 0, i = 2 // i = 1, i = 3
        int nowSafeCnt = preSafeCnt;
        boolean[][] nowVisited = getNowVisited(preVisited);
        for (int d = 0; d < 2; d++) // 2번은 '좌우' 혹은 '상하'가 짝이므로 이중 포문으로 짝이 나올 수 있도록 2d + k 설정
            nowSafeCnt = viewToDir(row, col, DR[k + 2 * d], DC[k + 2 * d], nowSafeCnt, nowVisited);
        dfs(idx + 1, nowSafeCnt, nowVisited);
    }
}

예를 들어 cctv 번호가 1번이라면, 상 하 좌 우 하나의 방향으로만 이동이 가능합니다. 따라서 for(int k = 0 ~) 단일 포문으로  viewToDir로 탐색을 진행하고 dfs를 적용할 수 있습니다.

하지만 cctv 번호가 2번이라면, '좌우', '상하'가 하나의 묶음입니다. 따라서, 이중 for문으로 

row가 위, 아래  // col이 좌, 우로 움직일 수 있도록 k + 2 * d로 인덱스를 설정하였습니다.

그 결과, 만약 k = 0라면,

if d == 0: k + 2 * d = 0         ----> DR[0] = -1, DC[0] = 0

if d == 1: k + 2 * d = 2         ----> DR[2] = 1,  DC[2] = 0 

좌우로 움직일 수 있는 공식을 만들 수 있었습니다.

이와 같은 방법으로 3, 4, 5 를 처리하면 DR, DC 로 모든 경우를 처리할 수 있습니다.

참조 #2

else if (value == 2) {
    for (int k = 0; k < 2; k++) { // 짝 i = 0, i = 2 // i = 1, i = 3
        int nowSafeCnt = preSafeCnt;
        boolean[][] nowVisited = getNowVisited(preVisited);
        for (int d = 0; d < 2; d++) // 2번은 '좌우' 혹은 '상하'가 짝이므로 이중 포문으로 짝이 나올 수 있도록 2d + k 설정
            nowSafeCnt = viewToDir(row, col, DR[k + 2 * d], DC[k + 2 * d], nowSafeCnt, nowVisited);
        dfs(idx + 1, nowSafeCnt, nowVisited);
    }
}

이 코드를 살펴보면, nowSafeCnt로 지역변수를 바깥 for문 내에서 적용하는 것을 볼 수 있습니다. 

안쪽의 for (int d = 0 ~ )는 cctv가 탐색할 수 있는 방향의 묶음이므로

nowSafeCnt, nowVisited에 한 묶음이 모두 영향을 받아야 합니다.

하지만, k가 바뀐다면, 이는 곧 아예 탐색하는 방법을 바꾸는 것을 의미합니다.

즉, k = 0 이라면 좌우를 의미하는데, k = 1이라면 상하를 의미합니다.

따라서, 회전은 다른 경우의 수로 보아야 하기 때문에 독립성을 보장받아야 합니다. 이전의 nowSafeCnt는 영향을 주면 안 되므로 preSafeCnt를 재할당하고, preVisited를 깊은 복사 하여 for문의 이전 인덱스에 변경된 값이 영향을 주지 않도록 해야 합니다.

참조 #3

int viewToDir(int row, int col, int dr, int dc, int nowSafeCnt, boolean[][] nowVisited) {
    while(true) {
        row += dr; // row에 값 업데이트
        col += dc; // col에 값 업데이트

        if (!isValid(row, col)) break; // 만약 벽이거나 유효한 인덱스가 아니라면 종료
        if (!nowVisited[row][col] && map[row][col] == 0) { // 방문하지 않은 경우에만 참조#4
            nowVisited[row][col] = true;
            nowSafeCnt++;
        }
    }
    return nowSafeCnt;
}

row, col은 행과 열을 의미하고, dr dc는 DR, DC로 이동한 값을 의미합니다. 

while문으로 row, col을 업데이트하되, 만약 유효한 인덱스가 아니거나, 벽을 만난다면 break 하여 더 이상 방문 처리가 되지 않도록 합니다. 만약 아직 방문하지 않았고, map 값이 0이라면 nowSafeCnt를 1 추가합니다. 

여기서, 중요한 점은 '방문'이라는 것입니다. 방문하지 않은 경우에만 nowSafeCnt를 증가시키는 이유는 

5와 2가 인접한 경우  ### 5 2 ###   처럼 5 와 2는 같은 방향을 공유할 수 있기 때문입니다. 

따라서, 중복을 방지하기 위해 방문하지 않은 경우만 ++할 수 있도록 하였습니다.

이상으로 SW 기출문제 감시 - 자바 풀이를 마치도록 하겠습니다.

감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 톱니바퀴 자바 풀이를 진행하고자 합니다.!

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

1. 풀이 소스:

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Gear gear = new Gear();
        for (int i = 0; i < 4; i++) {
            String gearStatus = br.readLine();
            for (int j = 0; j < 8; j++) {
                gear.addStatus(i, j, gearStatus.charAt(j));
            }
        }

        int k = parseInt(br.readLine());
        for (int i = 0; i < k; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            gear.setRotate(parseInt(st.nextToken()), parseInt(st.nextToken()));
        }

        gear.run();

        System.out.println(gear.getScore());
    }
}

class Gear {

    int[][] map = new int[4][8];
    Queue<Rotate> rotates = new ArrayDeque<>();
    Gear(){}

    void addStatus(int row, int col, char status) {
        map[row][col] = Character.getNumericValue(status);
    }

    void setRotate(int number, int dir) {
        rotates.add(new Rotate(number - 1, dir)); // 번호가 1부터인데 인덱스는 0부터 설정
    }

    void run() { // 극 N = 0, S = 1  dir:  시계 = 1, 반시계 = -1
        while (!rotates.isEmpty()) {
            Rotate rt = rotates.poll();
            int number = rt.number;
            int dir = rt.dir;

            int two = map[number][2];
            int six = map[number][6];

            rotate(number, dir);

            if (number == 0) dfs(number + 1, two, dir, false); // 오른쪽으로 이동하면서 회전
            else if (number == 3) dfs(number - 1, six, dir, true); // 왼쪽으로 이동
            else { // 1, 2는 양쪽 방향으로 진행
                dfs(number + 1, two, dir, false);
                dfs(number - 1, six, dir, true);
            }
        }
    }

    void rotate(int number, int dir) { // 극 N = 0, S = 1  dir:  시계 = 1, 반시계 = -1
        int[] tmp = map[number].clone(); // 복사 배열
        if (dir == 1) { // 시계
            // 이전항이 자신의 항
            System.arraycopy(tmp, 0, map[number], 1, 7);
            map[number][0] = tmp[7];
        } else { // 반시계
            // 다음 항이 자신의 항
            System.arraycopy(tmp, 1, map[number], 0, 7);
            map[number][7] = tmp[0];
        }
    }

    // 극이 달라야 회전
    void dfs(int nowNum, int prePole, int preDir, boolean toLeft) {
        if (nowNum == -1 || nowNum == 4) return;
        int nowDir = preDir == 1 ? -1 : 1; // 역방향

        int two = map[nowNum][2]; // 회전 시키기 전 고정 값
        int six = map[nowNum][6];

        if (toLeft) { // 영향 주는 곳은 6, 받는 곳은 2
            if (prePole == two) return; // 극이 같기에 더 이상 진행 x

            rotate(nowNum, nowDir); // 극이 다르다면 방향과 다르게 진행 회전
            dfs(nowNum - 1, six, nowDir, true); // 번호를 낮춰서, 다음 재귀

        } else { // 오른쪽으로 이동시 영향 주는 곳은 2, 받는 곳 6
            if (prePole == six) return; // 극이 같기에 더 이상 진행 x

            rotate(nowNum, nowDir);
            dfs(nowNum + 1, two, nowDir, false);
        }
    }

    int getScore() {  // 극 N = 0, S = 1  dir:  시계 = 1, 반시계 = -1
        int score = 0;

        score += map[0][0] == 0 ? 0 : 1;
        score += map[1][0] == 0 ? 0 : 2;
        score += map[2][0] == 0 ? 0 : 4;
        score += map[3][0] == 0 ? 0 : 8;

        return score;
    }

    class Rotate {
        int number;
        int dir;

        Rotate (int number, int dir) {
            this.number = number;
            this.dir = dir;
        }
    }
}

2.  풀이 중점 사항

해당 문제는 재귀를 활용하여 톱니바퀴 회전 가능 여부를 확인하고 회전하는 방법으로 문제를 해결할 수 있습니다.

0, 3의 인덱스를 가진 톱니바퀴(문제 1번,  4번 톱니바퀴)는 각 단방향으로만 영향을 줄 수 있습니다.

•  인덱스 0번 톱니바퀴는 오른쪽 톱니바퀴에 영향
•  인덱스 3번 톱니바퀴는 왼쪽 톱니바퀴에 영향
•  인덱스 1번, 인덱스 2번 톱니바퀴는 왼쪽, 오른쪽 각각 모두 영향을 줍니다.

이 영향성을 가지고 문제 해결 전략을 세울 수 있습니다.

• 먼저, 회전할 톱니바퀴 인덱스와 방향을 큐에 넣습니다.
• 큐가 빌 때 까지 회전을 진행합니다.
• 큐에서 나온 톱니바퀴는 무조건 회전을 1회 진행합니다.
• 큐에서 나온 번호를 토대로 위에서 정의한 방법으로 재귀를 진행합니다.
• 중요한 점은 톱니바퀴에 영향을 주는 극은 회전 이전의 극입니다. 즉, 회전 이전에 영향을 주는 2번 인덱스와 6번 인덱스의 번호를 가진 톱니바퀴의 칸을 미리 변수로 설정한 후, 회전 이후의 값이 영향을 주지 않도록 합니다.
• 만약 왼쪽으로 톱니바퀴에 영향을 주는 재귀라면 이전 톱니바퀴의 6번 칸이 현재 톱니바퀴의 2번과 같은지 여부를 판단하고 회전을 시행합니다.
• 만약 오른쪽 톱니바퀴에 영향을 주는 재귀라면 이전 톱니바퀴의 2번 칸이 현재 톱니바퀴의 6번과 같은지 여부를 판단하고 회전을 시행합니다.
• 만약 인덱스가 -1 혹은 인덱스 4라면 재귀를 멈추고, 이전 톱니바퀴의 칸의 극과 현재 톱니바퀴의 칸 극이 같다면 재귀를 종료합니다.

rotate 메서드

void rotate(int number, int dir) { // 극 N = 0, S = 1  dir:  시계 = 1, 반시계 = -1
    int[] tmp = map[number].clone(); // 복사 배열
    if (dir == 1) { // 시계
        // 이전항이 자신의 항
        System.arraycopy(tmp, 0, map[number], 1, 7);
        map[number][0] = tmp[7];
    } else { // 반시계
        // 다음 항이 자신의 항
        System.arraycopy(tmp, 1, map[number], 0, 7);
        map[number][7] = tmp[0];
    }
}

회전할 때 중요한 점은 시계와 반시계 방향으로 회전할 때 이전 항 혹은 다음 항을 기억할 tmp 배열을 생성해야 합니다.

자바에서는 System.arraycopy() 메서드로 해결할 수 있습니다.

System.arraycopy(복사할 배열, 복사할 배열의 시작점, 복사될 배열, 복사될 배열의 시작점, 총 복사할 개수);

시계 방향의 경우 -> 방향이기 때문에 복사할 배열의 시작점은 0이 됩니다.

복사될 배열인 map[number]는 시작점이 1입니다.

즉, 0번의 인덱스 값이 1에 복사된다는 의미이므로 시계 방향 회전을 수행할 수 있고 복사할 개수가 7이므로

map[number][0]은 tmp[7]로 원형 시계를 설정할 수 있습니다.

dfs 메서드

 void dfs(int nowNum, int prePole, int preDir, boolean toLeft) {
    if (nowNum == -1 || nowNum == 4) return;
    int nowDir = preDir == 1 ? -1 : 1; // 역방향

    int two = map[nowNum][2]; // 회전 시키기 전 고정 값
    int six = map[nowNum][6];

    if (toLeft) { // 영향 주는 곳은 6, 받는 곳은 2
        if (prePole == two) return; // 극이 같기에 더 이상 진행 x

        rotate(nowNum, nowDir); // 극이 다르다면 방향과 다르게 진행 회전
        dfs(nowNum - 1, six, nowDir, true); // 번호를 낮춰서, 다음 재귀

    } else { // 오른쪽으로 이동시 영향 주는 곳은 2, 받는 곳 6
        if (prePole == six) return; // 극이 같기에 더 이상 진행 x

        rotate(nowNum, nowDir);
        dfs(nowNum + 1, two, nowDir, false);
    }
}

각 톱니바퀴는 회전 이전의 값을 반드시 가지고 있어야 합니다. 즉, 영향을 줄 수 있는 톱니바퀴가 회전한 결과를 넘겨준다면 문제에 위배되게 됩니다.

이를 구현하기 위해 two, six로 회전 이전의 값을 저장했습니다.

만약, toLeft == true로 왼쪽 방향으로 이동하는 것이라고 가정한다면,

먼저 prePole == two의 극을 비교합니다. prePole은 맞대는 이전 톱니바퀴의 6번 칸의 극을 의미합니다 (왼쪽으로 이동하므로 현재 톱니바퀴의 이전 톱니바퀴는 오른쪽에 위치합니다.)

두 극이 다르다면, 회전을 수행합니다.

왼쪽 방향성을 그대로 유지하면서, 톱니바퀴 번호는 하나 낮추고, 회전 이전의 값인 map[number][6], 현재 회전한 방향을 파라미터로 설정하여 재귀를 진행합니다.

이렇게 함으로써 다음 재귀가 실행될 때는, prePole을 받았을 때, 회전 이전의 값을 받을 수 있습니다.

이상으로 톱니바퀴 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 경사로 자바 풀이를 진행하고자 합니다.

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

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = parseInt(st.nextToken());
        int L = parseInt(st.nextToken());

        PathMap path = new PathMap(N, L);

        for (int row = 0; row < N; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < N; col++) {
                path.setMap(row, col, parseInt(st.nextToken()));
            }
        }

        System.out.println(path.calculatePossiblePath());
    }
}

class PathMap {
    int n; // n개
    int len; // 경사로 길이
    int[][] mapR; // 행 * 열
    int[][] mapC; // 열 * 행

    PathMap (int n, int len) {
        this.n = n;
        this.len = len;
        mapR = new int[n][n];
        mapC = new int[n][n];
    }

    void setMap(int row, int col, int value) {
        mapR[row][col] = value;
        mapC[col][row] = value;
    }

    int calculatePossiblePath() {
        int possiblePath = 0; // 최종 답

        for (int row = 0; row < n; row++) {
            if (isPossiblePath(mapR[row])) possiblePath++;
            if (isPossiblePath(mapC[row])) possiblePath++;
        }

        return possiblePath;
    }

    boolean isPossiblePath(int[] map) {
        int preH = map[0]; // 기준이 되는 높이
        int cnt = 1; // 경사로를 놓을 수 있는 길이 (초기화 1)

        for (int col = 1; col < n; col++) {
            if (preH == map[col]) cnt++; // 높이가 같다면 cnt 증가 (혹시 더 높은 높이가 나타나면 cnt로 판별)

            else if (preH + 1 == map[col]) { // 만약 이전보다 크다면
                if (cnt < len) return false; // 경사로를 놓을 수 있는 길이보다 짧다면
                preH++; // 기준점 업데이트 (높이 한칸 더 높게)
                cnt = 1; // 길이 초기화 (기준점은 아직 사다리를 안놓았으므로)
            }

            else if (preH - 1 == map[col]){ // 이전 높이가 더 크다면

                int nowCnt = 1;
                int nowH = map[col]; // 현재 높이를 기준으로 len개까지 같은 높이가 나와야 함

                for (int k = col + 1; k < n; k++) { // 다음 행 부터 개수 세기
                    if (nowH != map[k]) break; // 현재 높이와 같지 않은 경우
                    nowCnt++;
                    if (nowCnt >= len) break; // 경사로를 놓을 수 있는 길이 이상이 되면
                }
                if (nowCnt < len) return false; // 이보다 적은 경우 종료

                col += (len - 1); // col을 포함한 열부터 경사로를 놓으므로
                cnt = 0; // 새로 시작하는 지점은 이미 경사로가 놓여있으므로
                preH = nowH;
            }

            else return false;
        }
        return true;
    }
}

2. 풀이 중점 사항

처음에 문제를 접근할 때, 경사로를 놓게 되면 계속 유지되는 것이라고 판단하여 많은 시간을 소모하였습니다.

이후 문제를 다시 읽고 가능한 예시를 자세하게 보니 가능한 경우의 수 이므로 한 행 혹은 한 열 단위로 경사로를 놓을 수 있고,

놓은 사다리는 다른 행, 열에 영향을 주지 않는 것이었습니다. 따라서, visited와 같은 체크 변수는 필요하지 않았습니다. 

중요한 사항은 경사로를 설정하는 과정에서 이전 높이가 더 큰지 혹은 더 작은지, 같은지에 따라 다르게 분기를 처리해야 했습니다.

가능한 경우는 

• 이전 높이와 같음
• 이전 높이보다 1 큼
• 이전 높이보다 1 작음
• 그 외 모두 불가

이전 높이와 같음

이전 높이와 같다면, cnt++를 하여 혹여 이전 높이보다 1 크게 되는 상황에 대비해야 합니다.

이전 높이보다 1 큼

예를 들어 len = 3이고 높이가 3 3 3 4 라면

이전 높이가 같은 것이 3개가 있고 (cnt = 3) len과 같으므로 경사로를 놓을 수 있음을 의미합니다. 

preH++; cnt = 1; 를 설정하는 것은 현재 높이가 4이므로 이전 높이가 3인 것보다 1 크므로 업데이트를 하는 과정입니다.

cnt = 1은 경사로가 놓인 위치는 3 3 3입니다. 한 칸 높은 곳은 경사로가 놓이지 않으므로  해당 위치는 경사로를 놓을 수 있는 유효한 칸이기 때문에 cnt++를 합니다.

이전 높이보다 1 작음

이전 높이보다 1이 작은 경우는, 현재 위치한 높이를 nowH로 설정하여

for 문으로 col을 nowH와 다를 때까지 이동하여야 합니다.

else if (preH - 1 == map[col]){ // 이전 높이가 더 크다면

    int nowCnt = 1;
    int nowH = map[col]; // 현재 높이를 기준으로 len개까지 같은 높이가 나와야 함

    for (int k = col + 1; k < n; k++) { // 다음 행 부터 개수 세기
        if (nowH != map[k]) break; // 현재 높이와 같지 않은 경우
        nowCnt++;
        if (nowCnt >= len) break; // 경사로를 놓을 수 있는 길이 이상이 되면
    }
    if (nowCnt < len) return false; // 이보다 적은 경우 종료

    col += (len - 1); // col을 포함한 열부터 경사로를 놓으므로
    cnt = 0; // 새로 시작하는 지점은 이미 경사로가 놓여있으므로
    preH = nowH;
}

여기서 nowCnt가 len 이상이 되면 break를 하여 더 이상 탐색되지 않도록 합니다.

col += (len - 1)을 하는 이유는 다음과 같습니다.

만약 len = 3이고, 인덱스는 0 1 2 3 이고, 해당 높이는 4 3 3 3입니다.

인덱스 1이 인덱스 0인 높이 4보다 1 작으므로 인덱스 3까지 탐색하였고

nowCnt == len 이여서 경사로를 놓았다고 가정하겠습니다.

이 경우 4 경 경 경 이 됩니다.

col은 기존에 인덱스 1이었고, 인덱스 3까지 경사로를 놓게 됩니다. 

이때, 기존 높이는 preH가 nowH로 업데이트하고 인덱스 3까지 경사로를 놓았으므로  인덱스 3은 더 이상 경사로를 

놓을 수 없으므로 0으로 cnt를 초기화하게 되는 것입니다.!

나머지 자세한 풀이는 주석화 하였습니다.

이상으로 경사로 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 - 로봇 청소기 자바 풀이를 진행하고자 합니다.

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

1. 풀이 소스

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int r = parseInt(st.nextToken());
        int c = parseInt(st.nextToken());
        int dir = parseInt(st.nextToken());

        RobotCleaner robot = new RobotCleaner(n, m);
        robot.setPoint(r, c, dir); // 처음 위치 및 방향 초기화

        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++) {
                robot.setMap(row, col, parseInt(st.nextToken()));
            }
        }

        robot.run(); // 작동 시작

        System.out.println(robot.getCleanRoom());

    }
}

class RobotCleaner {

    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};

    int n; // 행 개수
    int m; // 열 개수
    int[][] map; // 벽 혹은 이동 가능 영역 표시
    Point point; // 현재 위치
    int nowDir; // 북: 0, 동: 1, 남: 2,  서: 3
    int cleanRoom; // 총 청소한 구역
    boolean[][] visited; // 청소한 지역 (방문한다면 청소 해야 함)

    RobotCleaner (int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m];
        visited = new boolean[n][m];
    }

    void setPoint(int row, int col, int dir) {
        point = new Point(row, col);
        nowDir = dir;
    }

    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }

    void run() {
        while(true) {

            int row = point.row; // point가 변경될 수 있으므로 임시 row
            int col = point.col; // 임시 col

            // 움직일 수 있고, 방문을 안했다면(청소가 가능하다면) <1>
            if (map[row][col] == 0 && !visited[row][col]) {
                cleanRoom++;
                visited[row][col] = true; // 방문 처리
            }

            boolean isNotCleanRoom = false; // 방문 가능한 곳 체크
            for (int i = 0; i < 4; i++) {
                int possibleR = row + DR[i];
                int possibleC = col + DC[i];

                if (!isValid(possibleR, possibleC)) continue; // 불가능한 곳

                isNotCleanRoom = true; // 청소할 곳 있음 <2> // isNotCleanRoom
                break;
            }

            if (isNotCleanRoom) {
                rotate(); // 회전하기

                //북: 0, 동: 1, 남: 2,  서: 3 이동하기
                if (nowDir == 0) row--; // 북 방향에서 한 칸 앞은 행 기준 --
                else if (nowDir == 1) col++; // 동 방향(오른쪽) 한 칸 앞
                else if (nowDir == 2) row++; // 남 기준 앞 row++
                else  col--; // 서 방향 기준 앞은 왼쪽

                if (!isValid(row, col)) continue;
                point.row = row;// 가능한 경우 업데이트
                point.col = col;
            }

            else { // 현재 칸의 주변 중 청소되지 않은 빈 칸이 없는 경우 <2>

                //북: 0, 동: 1, 남: 2,  서: 3
                if (nowDir == 0) row++; // 북 방향에서 한 칸 뒤는 남쪽으로
                else if (nowDir == 1) col--; // 동 방향(오른쪽) 한 칸 뒤 왼쪽
                else if (nowDir == 2) row--;
                else  col++;

                if (!isPossibleBackMove(row, col)) return; // 후진 불가능
                point.row = row; // 후진 가능하다면 위치 업데이트 후 while문 돌아가기
                point.col = col;
            }
        }
    }

    boolean isValid(int row, int col) { // 유효한 범위 && 이동 가능하고 && 청소하지 않음
        return row >= 0 && row < n && col >= 0 && col < m &&
                map[row][col] == 0 && !visited[row][col];
    }

    boolean isPossibleBackMove(int row, int col) { // 유효한 범위 && 후진하는 곳은 벽이 아니여야 함
        return row >= 0 && row < n && col >= 0 && col < m &&
                map[row][col] == 0;
    }

    void rotate() {
        switch (nowDir) { // 북: 0, 동: 1, 남: 2,  서: 3 
            case 0:
                nowDir = 3; // 북 -> 서
                break;
            case 1:
                nowDir = 0; // 동 -> 북
                break;
            case 2:
                nowDir = 1; // 남 -> 동
                break;
            case 3:
                nowDir = 2; // 서 -> 남
                break;
        }
    }

    int getCleanRoom() {
        return cleanRoom;
    }

    class Point {
        int row;
        int col;

        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

2. 풀이 중점 사항

작동 사항 면밀하게 분석하기

해당 문제는 어떻게 코드를 작성해야 하는지 의사 코드를 명확하게 제시하고 있습니다. 따라서, 1 -> 2 or 3으로 반복적인 작업이 수행될 수 있도록 while 문 내부에서 적절한 분기 처리를 진행해야 합니다.

저는 2번 혹은 3번으로 분기가 처리되도록 하기 위해 isNotCleanRoom이라는 변수를 설정하였습니다.

총 4개의 상, 하, 좌, 우 에서 isValid() 메서드를 진행한 후, 만약 청소 가능한 구역이 하나라도 있다면 for문에서 빠져나와 isNotCleanRoom == true인 if 문으로 들어갑니다. 이후 회전을 진행하고 전진 여부를 판단하고 while문으로 돌아갑니다.

만약, 청소 가능한 구역이 없다면 isNotCleanRoom == false가 되어 후진 여부를 판단하여 while을 진행하거나 혹은 while을 종료합니다. 

그 외 부분은 자세한 주석으로 처리하였습니다.!

이상으로 로봇 청소기 자바 풀이를 마치도록 하겠습니다. 감사합니다.!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 - 연구소 자바 풀이를 진행하도록 하고자 합니다.

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

1. 풀이 소스 :

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        Lab lab = new Lab(n, m);
        
        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++)
                lab.setMap(row, col, parseInt(st.nextToken()));
        }
        
        lab.buildWall();
        System.out.println(lab.getSafeRegion());
    }
}

class Lab {
    
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};    
    
    int n; // row의 총 개수
    int m; // col의 총개수
    int minVirusCnt = Integer.MAX_VALUE; // 최소 바이러스 확진
    int virusCnt; // dfs로 실행된 각 조합에 바이러스 확진
    int[][] map; // 맵
    int wallsCnt = 3; // 벽의 개수 (무조건 3개를 세울 수 있으므로 초기화 3)
    
    boolean[][] visited; // 방문 여부
    List<Point> virus = new ArrayList<>(); // 바이러스 저장 리스트
    Combination combi; // 벽이 생성될 수 있는 조합
    
    Lab (int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m];
        visited = new boolean[n][m];
        combi = new Combination();
    }
    
    void setMap(int row, int col, int value) {
        map[row][col] = value;
        if (value == 0) combi.setInputs(new Point(row, col)); // 벽을 세울 수 있는 곳이라면 조합에 input 추가
        else if (value == 1) wallsCnt++; // 벽 개수 추가
        else virus.add(new Point(row, col)); // 바이러스 point 추가
    }
    
    void buildWall() {
        List<List<Point>> possibleCombi = combi.getCombination(); // 벽을 세울 수 있는 조합 생성
        
        for (List<Point> combis : possibleCombi) {
            for (Point point : combis) { // 각 조합에 있는 3가지 벽의 위치 하나씩
                map[point.row][point.col] = 1; // 벽 세우기
            }
            
            virusCnt = 0; // 각 조합 당 몇 개의 바이러스가 확진 되는지
            for (Point v : virus) {
                dfs(v.row, v.col); // dfs
            }
            
            minVirusCnt = Math.min(minVirusCnt, virusCnt); // 최소 바이러스 설정

            for (int row = 0; row < n; row++) {
                for (int col = 0; col < m; col++)
                    visited[row][col] = false; // 방문여부 다시 초기화
            }
            
            for (Point point : combis) {
                map[point.row][point.col] = 0; // 다시 벽 해제
            }
        }
    }
    
    void dfs(int row, int col) {
        
        visited[row][col] = true; // 방문 설정
        virusCnt++; // 바이러스 개수 증가
        
        for (int i = 0; i < 4; i++) {
            int nextR = row + DR[i]; // 다음 행
            int nextC = col + DC[i]; // 다음 열
            
            if (!isValid(nextR, nextC)) continue; // 이미 방문 혹은 인덱스 벗어났거나, 확진 가능한 곳이 아니라면
            dfs(nextR, nextC); // dfs
        }
    }
    
    int getSafeRegion() {
        return (n * m) - wallsCnt - minVirusCnt; // 총 안전 지대 = 총 장소 - 벽 - 확진자
    }
    
    boolean isValid(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < m && !visited[row][col] &&
            map[row][col] == 0; // 유효한 인덱스 && 방문 X && 감염 안된 사람들
    }
    
    static class Point {
        int row;
        int col;
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    
    static class Combination { // 조합 생성
        List<Point> inputs = new ArrayList<>(); // 조합에 사용될 인풋
        List<List<Point>> combi = new ArrayList<>(); // 최종 조합

        Combination () {}

        void setInputs(Point point) {
            inputs.add(point); // 리스트에 추가
        }

        List<List<Point>> getCombination() {
            getCombinationHelper(3, 0, new ArrayList<>()); // 조합 재귀 실행
            return combi;
        }

        void getCombinationHelper(int k, int start, List<Point> current) {
            if (k == 0) {
                combi.add(new ArrayList<>(current)); // 깊은 복사로 combi에 추가
                return;
            }
            
            for (int i = start; i < inputs.size(); i++) {
                current.add(inputs.get(i)); // input에 있는 값 조합에 추가
                getCombinationHelper(k - 1, i + 1, current); // 가능한 개수 줄이고, 다음 번 조합은 i를 증가 시켜서 실행
                current.remove(current.size() - 1); // [1, 2]이 조합에 있는 경우 다음 조합에 영향을 주지 않기 위해 [1]로 설정하여 다음 조합 실행
            }
        }
    }
}

2. 풀이 중점 사항

해당 문제는 안전 지대를 최대한 늘릴 수 있는 벽 3개를 짓고, 최대 안전지대 개수를 출력하는 문제입니다.

따라서, 벽을 지을 수 있는 곳 3가지의 조합을 생성한 후, 하나씩 dfs를 진행하여 최대 안전지대 개수를 구하는 방법으로 진행하였습니다.

조합

조합은 재귀로 생성할 수 있습니다. 3가지의 벽을 세워야 하는데, 이미 벽이 있거나 확진자가 존재하는 곳이 있기 때문에,
벽을 지을 수 있는 Point를 인풋으로 설정하여 List에 넣은 후, 각 리스트에 있는 원소를 재귀로 탐색하여 3가지의 배열을 설정하는 Combination 클래스를 static으로 선언하였습니다.

static class Combination { // 조합 생성 
    List<Point> inputs = new ArrayList<>(); // 조합에 사용될 인풋 
    List<List<Point>> combi = new ArrayList<>(); // 최종 조합 

    Combination () {}

    void setInputs(Point point) {
        inputs.add(point); // 리스트에 추가 
    }

    List<List<Point>> getCombination() {
        getCombinationHelper(3, 0, new ArrayList<>()); // 조합 재귀 실행 
        return combi;
    }

    void getCombinationHelper(int k, int start, List<Point> current) {
        if (k == 0) {
            combi.add(new ArrayList<>(current)); // 깊은 복사로 combi에 추가 
            return;
        }

        for (int i = start; i < inputs.size(); i++) {
            current.add(inputs.get(i)); // input에 있는 값 조합에 추가 
            getCombinationHelper(k - 1, i + 1, current); // 가능한 개수 줄이고, 다음 번 조합은 i를 증가 시켜서 실행 
            current.remove(current.size() - 1); // [1, 2]이 조합에 있는 경우 다음 조합에 영향을 주지 않기 위해 [1]로 설정하여 다음 조합 실행 
        }
    }
}

중점 사항은, 이전 블록 퍼즐 문제와 비슷한 방법으로 재귀로 하나의 원소를 더한 후, 재귀 이후 다시 원소를 하나 제거해야 하는 것입니다.

이 코드는 다음의 순서로 진행됩니다.

[1, 2] -> [1, 2, 3] , [1, 2, 4](return) ...... -> getCombinationHelper() 종료 -> current.remove(current.size() - 1)

==> [1] 

다음 i++로 인해 inputs.get(i) = 3

[1, 3]

따라서, 각 원소에 대한 모든 조합을 구할 수 있습니다.

DFS 빌드 업

void buildWall() {
    List<List<Point>> possibleCombi = combi.getCombination(); // 벽을 세울 수 있는 조합 생성

    for (List<Point> combis : possibleCombi) {
        for (Point point : combis) { // 각 조합에 있는 3가지 벽의 위치 하나씩 
            map[point.row][point.col] = 1; // 벽 세우기
        }

        virusCnt = 0; // 각 조합 당 몇 개의 바이러스가 확진 되는지 
        for (Point v : virus) {
            dfs(v.row, v.col); // dfs
        }

        minVirusCnt = Math.min(minVirusCnt, virusCnt); // 최소 바이러스 설정 

        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++)
                visited[row][col] = false; // 방문여부 다시 초기화 
        }

        for (Point point : combis) {
            map[point.row][point.col] = 0; // 다시 벽 해제
        }
    }
}

각 DFS 결과는 독립적으로 실행되어야 합니다. 예를 들어, 3가지의 조합 결과가 다음 3가지의 조합 결과에 영향을 주면 안 됩니다. 따라서, 모든 방문을 끝낸 이후, 최소 바이러스 확진 수를 구한 후, 방문 처리를 초기화하였습니다.

그리고 다시 벽을 해제하여, 다음 벽이 세워질 때 영향을 주지 않도록 하였습니다.

DFS

void dfs(int row, int col) {

    visited[row][col] = true; // 방문 설정 
    virusCnt++; // 바이러스 개수 증가 

    for (int i = 0; i < 4; i++) {
        int nextR = row + DR[i]; // 다음 행 
        int nextC = col + DC[i]; // 다음 열 

        if (!isValid(nextR, nextC)) continue; // 이미 방문 혹은 인덱스 벗어났거나, 확진 가능한 곳이 아니라면 
        dfs(nextR, nextC); // dfs 
    }
}

virusCnt는 인스턴스 변수로 설정되어 있기 때문에 각 dfs가 진행되더라도 전역적으로 공유하여 사용될 수 있습니다.

유효한 범위이고 방문하지 않았으며 확진 가능한 곳 (map[r][c] = 0)인 곳만 다음 dfs로 탐색을 진행할 수 있습니다.

나머지 자세한 부분은 주석화 하였습니다. 

이상으로 SW 기출문제 연구소 풀이를 마치도록 하겠습니다. 감사합니다.

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 테트로미노 자바 풀이를 작성하고자 합니다.

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

1. 풀이 소스

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        Board board = new Board(n, m);
        
        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++) {
                board.setMap(row, col, parseInt(st.nextToken()));
            }
        }
        
        board.run();
        
        System.out.println(board.getMaxSum());
    }
}

class Board{
    
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, -1, 0, 1};
    
    int n; // 행의 개수
    int m; // 열의 개수
    int maxSum; // 최대 값
    int[][] map; // 각 행과 열에 해당하는 값을 저장할 2차원 배열
    boolean[][] visited; // 방문 여부
    
    Board(int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m];
        visited = new boolean[n][m];
    }

    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }

    void run() {
        
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                int count = 1; // 시작은 1로 설정
                int sum = map[row][col]; // 합 초기화

                visited[row][col] = true; // 맨 처음 선택하는 좌상단 좌표는 방문처리
                dfs(row, col, sum, count); // dfs 시작
                visited[row][col] = false; // dfs 종료 후 맨 처음 선택한 시작점 방문 해제
            }
        }
    }
    
    void dfs(int row, int col, int sum, int count) {
        
        if (count == 4) {
            maxSum = Math.max(maxSum, sum); // 최대 값 구하기
            return; // 재귀 종료
        }

        for (int i = 0; i < 4; i++) {
            int nextR = row + DR[i]; // 이동할 row  
            int nextC = col + DC[i]; // 이동할 col

            if (!isValid(nextR, nextC)) continue; // 유효한 범위가 아니거나 이미 방문한 경우

            if (count == 2) { // 만약 2라면 이전 행과 열에서 한 번 더 움직일 수 있도록 row, col로 연결 
                visited[nextR][nextC] = true;
                dfs(row, col, sum + map[nextR][nextC], count + 1);
                visited[nextR][nextC] = false;
            }

            visited[nextR][nextC] = true; // 방문 여부 표시
            dfs(nextR, nextC, sum + map[nextR][nextC], count + 1); // dfs 재귀
            visited[nextR][nextC] = false; // 현재 방문한 곳 false 표시
        }
    }
    
    boolean isValid(int row, int col) { // 유효한 범위에 아직 방문하지 않은 경우 
        return row >= 0 && row < n && col >= 0 && col < m && !visited[row][col];
    }
    
    int getMaxSum() {
        return this.maxSum;
    }
    
}

2. 풀이 중점 사항

해당 문제는 DFS로 완전탐색을 진행하되 블록의 규칙을 찾을 수 있어야 했습니다.

***  *     *  ***   **  **   *    * 
*    *** ***    *    *  *    *    *
                     *  *    **  **

*    *  **    **  
**  **   **  **   
 *  *       

*    *   *  ***
**  **  ***  *
*    *


****

*
*
*
* 

**
**

해당 블록을 자세히 보면, 특정 점을 시작으로 마치 방문하지 않은 노드를 방문하는 것처럼 이뤄진 것을 확인할 수 있습니다.

예를 들어 아래의 블록들이 있다면 해당 블록은 x x x에서 파생된 것이라고 볼 수 있습니다.

x  x  x   |    x   x   x   x   |    x        

        x   |                       |    x  x  x   

이는 방문하지 않은 곳으로 노드를 옮겨가며 총 4번만 움직이면 ㅜ, ㅗ, ㅏ, ㅓ 를 제외한 블록은 모두 이동할 수 있음을 의미합니다.

ㅏ, ㅗ, ㅓ, ㅜ 는 다음의 방법으로 이동할 수 있습니다.

두번째 이동하는 장소에서  다음으로 이동할 때, nextR, nextC에 대한 map의 합을 구한 후, 경로를 row, col로 설정하는 것입니다.

    for (int i = 0; i < 4; i++) {
        int nextR = row + DR[i]; // 이동할 row  
        int nextC = col + DC[i]; // 이동할 col

        if (!isValid(nextR, nextC)) continue; // 유효한 범위가 아니거나 이미 방문한 경우

        if (count == 2) { // 만약 2라면 이전 행과 열에서 한 번 더 움직일 수 있도록 row, col로 연결 
            visited[nextR][nextC] = true;
            dfs(row, col, sum + map[nextR][nextC], count + 1);
            visited[nextR][nextC] = false;
        }

        visited[nextR][nextC] = true; // 방문 여부 표시
        dfs(nextR, nextC, sum + map[nextR][nextC], count + 1); // dfs 재귀
        visited[nextR][nextC] = false; // 현재 방문한 곳 false 표시
    }

이 그림과 함께 해당 코드를 살펴보면, row, col을 다시 dfs의 재귀 위치로 설정함으로써, 4개를  방문한 후 maxSum 처리를 할 수 있습니다.

    visited[nextR][nextC] = true; // 방문 여부 표시
    dfs(nextR, nextC, sum + map[nextR][nextC], count + 1); // dfs 재귀
    visited[nextR][nextC] = false; // 현재 방문한 곳 false 표시

다음과 같이 방문 처리 후 다시 방문을 푸는 재귀를 위해 이동한 4개의 움직임이 visited[row][col] = true로 계속 유지된다면
하나의 경로가 끝난 후 실행되는 다음 dfs에 영향을 줄 수 있습니다.

따라서,  count == 4가 된다면 maxSum을 업데이트하기 때문에 현재 방문 여부는 return; 이후 visited[row][col] = false로 처리함으로써 다시 리셋할 수 있게 됩니다.

이상으로 백준 테트로미노 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 주사위 굴리기 자바 풀이를 작성하도록 하겠습니다.

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

1, 풀이 소스

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        int r = parseInt(st.nextToken());
        int c = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());

        Board board = new Board(n, m);
        board.setPoint(r, c);

        for (int row = 0; row < n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < m; col++) {
                board.setMap(row, col, parseInt(st.nextToken()));
            }
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            board.addCommand(parseInt(st.nextToken()));
        }

        board.run();
        System.out.print(board.printUpNumber());
    }
}

class Board {
    int n;
    int m;
    Point point;
    int[][] map;
    int[] dice;
    Queue<Character> cmds = new ArrayDeque<>();
    List<Integer> upNumbers = new ArrayList<>();

    Board (int n, int m) {
        this.n = n;
        this.m = m;
        map = new int[n][m]; // (0, 0) 부터 시작
        dice = new int[6]; // front, bottom, back, up, left, right
    }

    void setPoint(int row, int col) {
        point = new Point(row, col);
    }

    void setMap(int row, int col, int value) {
        map[row][col] = value;
    }

    void addCommand(int cmd) {
        switch (cmd) {
            case 1:
                cmds.add('E');
                break;
            case 2:
                cmds.add('W');
                break;
            case 3:
                cmds.add('N');
                break;
            case 4:
                cmds.add('S');
                break;
        }
    }

    void run() {

        while(!cmds.isEmpty()) {
            char command = cmds.poll();
            int row = 0;
            int col = 0;

            switch (command) {
                case 'E': // 동쪽은 열++
                    col++;
                    break;
                case 'W': // 서쪽은 열--
                    col--;
                    break;
                case 'N': // 북쪽은 행 -- (위로 올리므로)
                    row--;
                    break;
                case 'S': // 남쪽은 행 ++ (아래로 내려가므로)
                    row++;
                    break;
            }

            int nextR = point.row + row;
            int nextC = point.col + col;

            if (!isValid(nextR, nextC)) continue; // 유효하지 않은 명령어 패스

            rollDice(command); // 주사위 굴리기

            point.row = nextR; // 주사위 위치 row 이동시키기
            point.col = nextC; // 주사위 위치 col 이동시키기

            if (map[point.row][point.col] == 0) {
                map[point.row][point.col] = dice[1]; // 바닥에 주사위 값 복사
            } else {
                dice[1] = map[point.row][point.col]; // 바닥에 있는 값을 주사위애 복사
                map[point.row][point.col] = 0; // 칸 값 0
            }

            upNumbers.add(dice[3]); // 상단에 있는 주사위 값 upNumbers에 추가
        }
    }

    boolean isValid(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < m;
    }

    void rollDice(char command) {
        // front(0), bottom(1), back(2), up(3), left(4), right(5) 회전 마침
        int up = dice[3];
        int bottom = dice[1];
        int left = dice[4];
        int right = dice[5];
        int front = dice[0];
        int back = dice[2];

        if (command == 'E') { // 왼쪽으로 회전
            dice[4] = up; // 왼 <- 위
            dice[1] = left; // 바 <- 왼
            dice[5] = bottom; // 오 <- 바
            dice[3] = right; // 위 <- 오
        }

        else if (command == 'W') { // 오른쪽으로 회전
            dice[5] = up; // 오 <- 위
            dice[1] = right; // 바 <- 오
            dice[4] = bottom; // 왼 <- 바
            dice[3] = left; // 위 <- 왼
        }

        else if (command == 'N') { // 북쪽으로
            dice[0] = bottom; // 앞 <- 바
            dice[3] = front; // 위 <- 앞
            dice[2] = up; // 뒤 <- 위
            dice[1] = back; // 바 <- 뒤
        }

        else if (command == 'S') {
            dice[0] = up; // 앞 <- 위
            dice[1] = front; // 바 <- 앞
            dice[2] = bottom; // 뒤 <- 바
            dice[3] = back; // 위 <- 뒤
        }
    }

    String printUpNumber() {
        StringBuilder sb = new StringBuilder();
        for (int num : upNumbers) sb.append(num).append("\n");
        return sb.toString();
    }

    class Point {
        int row;
        int col;

        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

2. 풀이 중점 사항

해당 문제는 회전 문제로, 주사위를 어떻게 회전시켜야 하는지가 중요한 과제입니다. 

먼저 방위표는 고정입니다. 즉 이전에 서쪽으로 이동하였더라도 방위표의 기준은 변하지 않습니다. 즉 서쪽 (컬럼 기준으로는 왼쪽으로 이동) 방향은 바뀌지 않습니다.

현재 위치한 지점으로 부터 동서남북 각 방향으로 이동한다고 했을 때, 명령어에 따라 주사위를 회전시켜야 합니다.

이후, 회전시킨 주사위를 이동시켜서 칸에 번호가 있는지 없는지 판단하고 바닥을 업데이트해야 합니다.

문제 풀이 의사코드는 다음과 같습니다.

• 각 방위에 대한 숫자형 데이터를 입력받고, 선호도에 따라 인트형 혹은 char형 등으로 이동 방향을 선입선출로 처리할 큐에 넣습니다.
• 큐가 빌 때까지 (방향) 루프를 진행합니다.
• 각 방위는 고정이므로 E, W, N, S에 따라 다음 이동할 nextR, nextCol을 조정합니다.
• 이동 불가능한 (인덱스를 벗어난) nextR, nextCol은 continue 하여 명령어를 넘깁니다.
• 이동 가능한 경우 rollDice()를 통해 주사위를 굴려서 각 주사위의 값을 회전시킵니다.
• 회전 시, 동 서 방향은 위, 바닥, 왼쪽, 오른쪽 면만 영향을 받습니다.
• 회전 시, 남 북 방향은 앞, 뒤, 위, 바닥 면만 영향을 받습니다.
• 회전을 마친 후, 구한 nextR, nextC을 현재 있는 point에 업데이트하여 이동을 시작합니다.
• 이동한 칸이 0이라면, 현재 주사위 상태의 바닥에 있는 값을 칸에 복사합니다.
• 이동한 칸이 0이 아니라면, 현재 주사위 상태의 바닥에 칸의 값을 복사하고, 칸은 0으로 만듭니다.
• 이동을 마쳤으므로 현재 주사위 상태의 윗면의 값을 upNumbers에 추가합니다.
• 큐가 비면, 윗면 리스트를 담은 upNumbers를 출력합니다.

방향성 

switch (command) {
    case 'E': // 동쪽은 열++
        col++;
        break;
    case 'W': // 서쪽은 열--
        col--;
        break;
    case 'N': // 북쪽은 행 -- (위로 올리므로)
        row--;
        break;
    case 'S': // 남쪽은 행 ++ (아래로 내려가므로)
        row++;
        break;
}

저는 이전에 이러한 이동 문제를 풀 때, x, y로 하려다 보니 항상 실수했던 경험이 있습니다. 따라서, row, col로 명확하게 명시하고 문제를 해결하다 보니 DB를 다룰 때처럼 자연스럽게 up 명령어는 row--를 실행하고 down 명령어는 row++를 처리하여 도중에 실수를 방지할 수 있었습니다.

주사위 회전

if (command == 'E') { // 왼쪽으로 회전
    dice[4] = up; // 왼 <- 위
    dice[1] = left; // 바 <- 왼
    dice[5] = bottom; // 오 <- 바
    dice[3] = right; // 위 <- 오
}

주사위 회전 시, 저는 이 부분이 항상 헷갈렸습니다. 따라서 저는 command == 'E'라는 식으로 명확하게 동쪽으로 회전하겠다는 것을 명시하여 혼돈을 줄이도록 작성을 했습니다.

왼쪽으로 주사위를 돌리면, 위쪽에 있던 면은 왼쪽으로 가므로 이러한 방식으로 회전을 처리하였습니다.

작성하다 보니 코드가 길어졌지만, 문제 자체가 난해하고 어렵기 때문에,

케이스를 명확하게 나누는 연습을 하였고, 쓰다가 제가 헷갈리는 것을 방지하기 위해 이왕이면 코드가 의미하는 바가 무엇인지 최대한 신경 써서 작성하려고 하였습니다.

이상으로 주사위 굴리기 문제를 마치도록 하겠습니다. 감사합니다.! 

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 - 뱀 자바 풀이를 진행하고자 합니다.!

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

1. 풀이 소스:

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

import static java.lang.Integer.parseInt;

public class Main {

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

        Game game = new Game(N); // game 인스턴스 선언

        StringTokenizer st;
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            game.setApple(parseInt(st.nextToken()), parseInt(st.nextToken())); // 사과 등록
        }

        int L = parseInt(br.readLine());
        for (int i = 0; i < L; i++) {
            st = new StringTokenizer(br.readLine());
            game.addDirection(parseInt(st.nextToken()), st.nextToken()); // 시간에 맞춰 변경해야하는 시간과 방향 설정
        }

        System.out.println(game.run());
    }
}

class Game {

    int n;
    int time; // 출력해야 하는 시간
    boolean[][] nowVisited; // 현재 뱀의 몸(머리, 꼬리 포함)이 걸쳐 있는지 판단
    boolean[][] map; // 사과 있는지 판단
    char nowDir = 'R'; // 현재 방향 (계속 바뀜)
    List<Tail> tails = new LinkedList<>(); // 꼬리 추가 및 삭제를 위한 링크드 리스트
    Queue<Direction> dirs = new ArrayDeque<>(); // 시간에 맞춰 방향 변경을 위한 큐

    Game (int n) {
        this.n = n;
        map = new boolean[n + 1][n + 1]; // n by n 이므로 n + 1로 초기화
        nowVisited = new boolean[n + 1][n + 1];
    }

    void setApple(int row, int col) {
        map[row][col] = true; // apple 설정
    }

    void addDirection(int ttl, String dir) {
        dirs.add(new Direction(ttl, dir)); // 시간에 맞는 방향 설정
    }

    int run() {

        int r = 1; // 행
        int c = 1; // 열
        tails.add(new Tail(r, c)); // 시작은 머리와 꼬리가 동일 하므로 꼬리에 추가

        while (true) { // 반복

            if (!dirs.isEmpty() && time == dirs.peek().ttl) { //비어 있지 않고 ttl와 같음
                Direction nextDir = dirs.poll(); // 다음 방향을 위한 Direction 인스턴스 큐에서 빼기

                if (nowDir == 'U') { // 각 방향에 맞춰 회전 후 방향 재조정
                    if (nextDir.dir.equals("L")) nowDir = 'L';
                    else nowDir = 'R';
                }

                else if(nowDir == 'D') {
                    if (nextDir.dir.equals("L")) nowDir = 'R';
                    else nowDir = 'L';
                }

                else if (nowDir == 'L') {
                    if (nextDir.dir.equals("L"))nowDir = 'D';
                    else nowDir = 'U';
                }

                else if (nowDir == 'R') {
                    if (nextDir.dir.equals("L")) nowDir = 'U';
                    else nowDir = 'D';
                }
            }

            // 회전을 마친 경우 혹은 회전이 없는 경우 nowDir에 방향에 맞춰 움직이기 시작
            switch (nowDir) {
                case 'U':
                    r--;
                    break;
                case 'D':
                    r++;
                    break;
                case 'L':
                    c--;
                    break;
                case 'R':
                    c++;
                    break;
            }

            if (!isValid(r, c)) { // 이동하려는 곳이 인덱스에 벗어나거나, 몸통이 있는 곳이라면 종료
                time++; // 종료시간은 마지막 움직이는 경우도 포함이므로
                break;
            }

            nowVisited[r][c] = true; // 머리가 방문한 곳 방문 추가

            // 위치한 곳에 사과가 있는지 파악하기
            if (!map[r][c]) { // 없다면 머리 증가 후 꼬리 제거
                tails.add(new Tail(r, c)); // 머리 추가

                Tail tail = tails.get(0); // 맨 마지막 꼬리 가져오기
                nowVisited[tail.r][tail.c] = false; // 꼬리가 사라지므로 false
                tails.remove(0); // 꼬리 제거
            }

            else {
                tails.add(new Tail(r, c)); // 사과가 있다면 머리 위치 추가
                map[r][c] = false; // 사과 제거하기
            }

            time++; // 모든 움직임이 끝났으므로 시간++
        }

        return time;
    }

    // 이미 몸체의 일부가 방문하고 있는 경우 종료
    boolean isValid(int r, int c) { // 맵의 유효한 범위에 아직 방문하지 않은 곳이여야
        return r > 0 && r <= n && c > 0 && c <= n && !nowVisited[r][c];
    }

    class Tail {
        int r; // row
        int c; // col

        Tail (int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    class Direction {
        int ttl; // time to live
        String dir; // 방향성

        Direction (int ttl, String dir) {
            this.ttl = ttl;
            this.dir = dir;
        }
    }
}

2. 풀이 중점 사항

해당 문제는 뱀이 움직일 때, 사과가 있는지 없는지 여부에 따라 몸통의 길이가 달라집니다.

따라서, 다음의 의사코드를 바탕으로 문제를 해결해야 합니다.

• 현재의 위치에서 방향을 먼저 설정하기
• 각 방향대로 움직이되, 보드 밖을 벗어나는 곳으로 이동하거나 혹은 이동한 곳에 뱀의 몸통이 존재한다면 종료하기
• 만약 움직인 곳이 유효하다면,
• 사과가 있다면 사과를 지우고 머리를 tails 링크드리스트에 추가하기, 현재 머리가 있는 곳에 몸통 여부 true 표시하기
• 사과가 없다면, 머리를 tails 링크드 리스트에 추가하고, 머리가 있는 곳에 몸통 여부 표시하기, 꼬리는 머리가 움직이므로 있던 장소에 몸통 여부를 false로 표시하고, tails에서 remove(0) 하기
• 모든 움직임이 마쳤으므로 시간을 ++ 하고 다시 while루프로 돌아가기

한 문제에 큐, 링크드리스트, 클래스, 이차원 배열, 방향 전환 등을 경험할 수 있는 좋은 시간이었던 것 같습니다.

자세한 풀이는 모두 주석으로 처리하였습니다.!

이상으로 뱀 자바 풀이를 마치도록 하겠습니다.

감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 - 2048(Easy)를 해결한 과정을 정리하고자 합니다.!

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

1. 풀이 소스:

package sw_12100.success;

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = parseInt(br.readLine());

        Board board = new Board(n);

        for (int i = 0 ; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                board.setBoard(i, j, parseInt(st.nextToken()));
            }
        }
        board.dfs(0);
        System.out.println(board.getAnswer());
    }
}

class Board {

    static final char[] DIR = {'U', 'D', 'L', 'R'}; // up, down, left, right

    int n;
    int answer;
    int[][] map;

    Board (int n) {
        this.n = n;
        map = new int[n][n];
    }

    void setBoard(int x, int y, int v) {
        map[x][y] = v;
    }

    int getAnswer() {
        return this.answer;
    }

    // dfs로 최대 5번 반복되는 과정에서 최대값 찾기
    void dfs(int step) {
        if (step == 5) { // count가 5라면 최대값 찾기
            for (int[] mapRow : map) {
                for (int num : mapRow) {
                    answer = Math.max(answer, num);
                }
            }
            return;
        }

        int[][] clone = new int[n][n];
        for (int i = 0; i < n; i++) {
            clone[i] = map[i].clone();
        }

        for (int i = 0; i < DIR.length; i++) { // 상 하 좌 우
            moveBlock(DIR[i]); // 블록 움직이기
            dfs(step + 1); // step 증가시켜서 다음 step 진행

            for (int j = 0; j < n; j++) map[j] = clone[j].clone();
        }
    }

    // block의 역할 --> 미는 블록이 두번 합쳐지더라도 다음 block을 0으로 만들어 세번 겹치지 않도록 보호
    void moveBlock(char dir) {
        if (dir == 'U') { // 블록을 위로 몰기 (낮은 행으로 몰기)
            for (int c = 0; c < n; c++) { // 선택된 맵의 열 (col)
                int row = 0;
                int block = 0;
                for (int r = 0; r < n; r++) { //선택된 맵의 행 (row)
                    if (map[r][c] != 0) { // 0이 아니라면 블록이 있음
                        if (map[r][c] == block) { // 블록과 선택한 블록이 같다면
                            map[row - 1][c] = block * 2; // 낮은 행으로 합치기
                            map[r][c] = 0; // 선택된 맵 위치 블록 0
                            block = 0; // 그 위치에 있는 블록 0
                        }

                        // 만약 r = 1, c = 1, row = 0 인 경우, 앞에 블록이 없으므로
                        // r = 0인 경우 map[r][c] != 0 통과, block은 0이 유지되므로
                        // 자연스럽게 블록이 없는 공간에 밀어넣게 됨 이후 row++
                        else {
                            block = map[r][c]; // 현재위치 블록 설정
                            map[r][c] = 0; // r, c 위치 0으로 설정하기
                            map[row][c] = block; // 위로 밀어서 블록 값을 위치 시키기 (이 경우 제자리에 위치할 수 있으므로 map[r][c]보다 뒤에 있어야 함!!!
                            row++; // 다음 밀 곳은 한 칸 아래로 내린 곳
                        }
                    }
                }
            }
        }

        else if (dir == 'D') { // 블록을 아래로 몰기
            for (int c = 0; c < n; c++) {
                int row = n - 1; // 처음으로 옮겨져야 하는 도착 위치는 마지막 행
                int block = 0;
                for (int r = n - 1; r >= 0; r--) {
                    if (map[r][c] != 0) {
                        if (map[r][c] == block) {
                            map[row + 1][c] = block * 2;
                            map[r][c] = 0;
                            block = 0;
                        }

                        else {
                            block = map[r][c];
                            map[r][c] = 0;
                            map[row][c] = block;
                            row--; // 다음 번 블록은 맨 아래 위치에서 한 칸 올린 곳
                        }
                    }
                }
            }
        }

        else if (dir == 'L') { // 블록을 왼쪽으로 몰기
            for (int r = 0; r < n; r++) {
                int col = 0; // 옮겨질 위치의 열
                int block = 0;
                for (int c = 0; c < n; c++) {
                    if (map[r][c] != 0) {
                        if (map[r][c] == block) {
                            map[r][col - 1] = block * 2;
                            map[r][c] = 0;
                            block = 0;
                        }
                        else {
                            block = map[r][c];
                            map[r][c] = 0;
                            map[r][col] = block;
                            col++;
                        }
                    }
                }
            }
        }

        else if (dir == 'R') { // 블록을 오른쪽으로 몰기
            for (int r = 0; r < n; r++) {
                int col = n - 1;
                int block = 0;
                for (int c = n - 1; c >= 0; c--) {
                    if (map[r][c] != 0) {
                        if (map[r][c] == block) {
                            map[r][col + 1] = block * 2;
                            map[r][c] = 0;
                            block = 0;
                        }

                        else {
                            block = map[r][c];
                            map[r][c] = 0;
                            map[r][col] = block;
                            col--;
                        }
                    }
                }
            }
        }
    }
}

2. 풀이 과정:

해당 문제는, 블록을 최대 5번까지 이동시킨 후, 블록에 최댓값을 구하는 것입니다. 최대 5번이므로 3번 4번에서도 최댓값이 나올 수 있지만, 블록을 합치는 것은 x, y 좌표에 대한 값 V는 증가함수 형태이므로 (양수의 값을 합치므로) 5번을 실행한 후 최댓값을 계산하면 중간 계산 과정을 생략할 수 있습니다.

배열 복제

제가 계속 실수 했던 부분은 배열 복제 부분입니다. map.clone()을 하게 되면 1차원 배열은 값이 복사되어 다른 배열을 생성할 수 있습니다. 하지만 map이 2차원 배열인 경우 참조를 복사하므로 '얕은 복사'가 수행되게 됩니다.

int[][] clone = new int[n][n];
for (int i = 0; i < n; i++) {
    clone[i] = map[i].clone();
}

 따라서, 다음과 같이 for문으로 1차원 배열 단위로 clone()하여 값이 복사될 수 있도록 처리해야 합니다.

헷갈리는 상 하 좌 우

상 하 좌 우를 처리하다보면 수학은 보통 (0, 0)이 아래에 위치합니다. 하지만 데이터베이스나 이러한 map 문제를 해결해야 할 때는 (0, 0) 혹은 (1, 1)이 왼쪽 상단에 위치하는 경우가 많습니다. 따라서, 행을 내려야 할 때, 혹은 행을 올려야 할 때 
Down 작업은 row++, Up 작업은 row-- 하는 것이 필요합니다.

이전에 i, j를 쓸 때는 이 과정이 너무 헷갈려서 추후 풀 때는, r, c로 설정하여 헷갈림이 덜 하도록 구현하였습니다.

블록 밀기

블록을 미는 과정에서 아래와 같은 소스가 있습니다. 해당 소스는 풀이 소스에 자세하게 주석처리 하였지만, 중요한 포인트는 block의 쓰임새입니다. 

for (int r = 0; r < n; r++) {
    int col = n - 1;
    int block = 0;
    for (int c = n - 1; c >= 0; c--) {
        if (map[r][c] != 0) {
            if (map[r][c] == block) {
                map[r][col + 1] = block * 2;
                map[r][c] = 0;
                block = 0;
            }

            else {
                block = map[r][c];
                map[r][c] = 0;
                map[r][col] = block;
                col--;
            }
        }
    }
}

열을 오른쪽으로 민다고 하는 것은 n - 1에서 시작해서 n - 2 -> n - 1 / n - 3 -> n -2 -> n - 1 (가능하다면) 이러한 방식으로 
밀어야 하는 곳의 가까운 곳에서부터 블록을 합쳐야 합니다.

만약 밀고자 하는 곳에서 값이 0이 아니라는 것은 블록이 있다는 것을 의미하고,

해당 위치가 블록의 값과 같다면 블록에 2배를 합니다.

이 후, 블록을 0으로 설정하는데, 이는 무조건 다음 혹은 이후에 실행되는 반복에서 아래의 코드가 실행되는 것을 방지합니다.

map[r][c] != 0 && map[r][c] == block

블록이 0이 되어 있으므로 map[r][c]가 == 0이라면 다음 반복으로 넘어가므로, 블록이 값을 가져야만 해당 구문이 실행될 수 있습니다. 따라서, 새로운 값으로 블록을 생성해야 하므로, 블록을 미는 과정에서 3번 이상 겹치는 일이 발생하지 않습니다.

이상으로 2048 문제 풀이를 마치도록 하겠습니다.! 감사합니다 !!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 SW 기출문제인 구슬 탈출2 문제를 해결하는 과정을 정리하도록 하겠습니다.

문제 출처: 

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

1. 풀이 소스 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        Board board = new Board(n, m);
        
        for (int i = 0; i < n; i++) board.setMap(br.readLine(), i);
        board.moveMarble();
        System.out.println(board.getAnswer());
    }
}

class Board {
    
    static final int[] DX = {-1, 0, 1, 0};
    static final int[] DY = {0, -1, 0, 1};
    
    int n, m;
    Marble redMarble, blueMarble;
    char[][] map;
    boolean[][][][] visited; // Red, Blue 구슬의 각 각 x, y의 방문 여부
    int answer = -1;
    
    Board(int n, int m) {
        this.n = n;
        this.m = m;
        map = new char[n][m];
        visited = new boolean[n][m][n][m];
    }
    
    void setMap(String str, int idx) {
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            map[idx][i] = ch;
            
            if (ch == 'R') redMarble = new Marble(idx, i, 0);
            else if (ch == 'B') blueMarble = new Marble(idx, i, 0);
        }
    }
    
    void moveMarble() {

        Queue<Marble> redQ = new ArrayDeque<>();
        Queue<Marble> blueQ = new ArrayDeque<>();
        
        redQ.add(redMarble);
        blueQ.add(blueMarble);
        
        while(!redQ.isEmpty() && !blueQ.isEmpty()) {
            Marble red = redQ.poll();
            Marble blue = blueQ.poll();

            if (red.step > 10) { // bfs 원리로 인해 x 위치에서 -1, +1 등을 수행하더라도 각 움직인 위치는 step + 1
                answer = -1;
                return;
            }
            
            // 파란색이 0에 도착한 경우
            if (map[blue.x][blue.y] == 'O') continue; // 다른 방법이 존재할 수 있으므로 해당 경로로 진행하는 것만 중지
            
            // 파란색이 도착하지 않고 빨간색이 O에 도착한 경우
            if (map[red.x][red.y] == 'O') {
                answer = red.step;
                return;
            }    
            
            for (int i = 0; i < 4; i++) {
                int bx = blue.x; // 반드시 blue부터 실행
                int by = blue.y; 

                boolean isBlueCheck = false; // 파란 구슬이 'O'에 들어가는지 체크

                while (true) {
                    bx += DX[i];
                    by += DY[i];
                    
                    if (map[bx][by] == 'O') {
                        isBlueCheck = true;
                        break;
                    }
                    
                    else if (map[bx][by] == '#') {
                        bx -= DX[i];
                        by -= DY[i];
                        break;
                    }
                }

                if (isBlueCheck) continue; // 만약 'O'에 파란 구슬이 도착하는 경우 선행 조건과 관계없이 queue에 넣지 않음
                
                int rx = red.x;
                int ry = red.y;
                
                while(true) {
                    rx += DX[i];
                    ry += DY[i];
                    
                    if (map[rx][ry] == 'O') break;
                    else if (map[rx][ry] == '#') {
                        rx -= DX[i];
                        ry -= DY[i];
                        break;
                    }
                }
                
                // 두개의 위치가 같다면 
                // 서로 다른 큐에 의해 구슬의 앞 뒤 관계를 고려하지 않고 이동하였으므로
                // 두 구슬의 우선순위에 따라 배치를 다르게 해야 함
                if (bx == rx && by == ry && map[rx][ry] != 'O') {
                    
                    // 맨해튼 거리 공식을 쓰는 이유 -> x, y 가 한칸씩 움직일 수 있으므로
                    int redDist = Math.abs(red.x - rx) + Math.abs(red.y - ry);
                    int blueDist = Math.abs(blue.x - bx) + Math.abs(blue.y - by);
                    
                    if (redDist > blueDist) {
                        rx -= DX[i];
                        ry -= DY[i];
                    } else {
                        bx -= DX[i];
                        by -= DY[i];
                    }
                }
                
                if (!visited[rx][ry][bx][by]) {
                    visited[rx][ry][bx][by] = true;
                    
                    redQ.add(new Marble(rx, ry, red.step + 1));
                    blueQ.add(new Marble(bx, by, blue.step + 1));
                }
            }
        }
    }
    
    int getAnswer() {
        return this.answer;
    }
    
    class Marble {
        int x;
        int y;
        int step;
        
        Marble(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
}

2. 풀이 과정

해당 문제는 해결하지 못하여 하단의 블로그를 참고하였습니다. 

풀이 중점 사항은 다음과 같습니다.

빨간 구슬, 파란 구슬을 저장할 Queue를 각각 선언합니다.

빨간 구슬, 파란 구슬이 움직일 때, 상하좌우 인접한 곳에 구슬이 있다면 이동에 제약이 생길 수 있습니다.

이를 모두 한 번에 고려하게 된다면 복잡해지기 때문에, 하나의 통일된 조건으로 묶어서 판단할 수 있습니다.

• 상하좌우로 각 구슬을 각 각 이동시킵니다.
• 예를 들어 위로 구슬을 이동시킬 경우, 빨강, 파랑 구슬은 동시에 위로 올라가게 됩니다.
• 위치한 곳이 서로 다르다면, 겹치는 경로로 움직이지 않았음을 의미합니다.
• 만약 이동한 곳이 동일하다면, 두 구슬은 인접한 곳에서 겹치는 경로로 이동하였음을 의미합니다.
• 겹치는 경로로 이동한 경우 어떤 구슬이 앞 서 있었는지 판단하기 위해 맨해튼 거리 공식을 활용하여 최초 출발한 위치에서 도착한 위치를 빼서 더 먼 구슬은 도착한 위치 -1을 합니다.
• 이동하는 순서는 반드시 파란 구슬부터 진행하여, 만약에 파란 구슬이 이동하는 시점에 'O'를 마주한다면 queue에 넣지 않고 continue 합니다.
• 한 번 설정한 좌표를 토대로 while문으로 장애물 혹은 'O'을 만날 때까지 반복하는 과정에서 파란 구슬은 빨간 구슬의 선행 조건에 상관없이 'O'에 도착한다면 종료합니다.
• 그 이유는 'O'에 빨간 구슬이 도착하든 혹은 파란 구슬이 먼저 도착하든 구슬은 빠져나가게 되어있습니다. 따라서, 빨간 구슬이 선행되어 있더라도 파란 구슬이 이어서 'O'에 오게 되므로 종료시킵니다.
• 반면, 빨간 구슬이 'O'에 도착한 경우 바로 return 하지 않는 이유는 queue에 넣는 조건이 red.step > 10이므로 큐에서 나와 들어갔을 때는, step이 10일 수도 있습니다. 따라서, step + 1인 경우 11이므로 -1을 리턴해야 할 수 있습니다.
• 해당 조건 코드는 queue에서 나올 때 검증하므로 while문에는 작성하지 않았습니다.

중요한 포인트는, bfs를 구현하기 위해 방문 위치를 4차원 배열로 설정하여 방문한 곳에 동일하게 방문하는 것을 방지해야합니다. 나아가, 두 큐를 분리하였기 때문에 두 구슬이 동일한 위치에 도착한다면 선행 조건을 파악하기 위해 맨해튼 거리 공식을 적용해야 했습니다.

많이 어려웠던 문제였고 해이해진 정신을 바로잡을 수 있는 기회였습니다.

이상으로 SW 기출문제 구슬 탈출2 문제 풀이를 마치겠습니다. 감사합니다.!!!

참고 블로그: https://wellbell.tistory.com/44