[알고리즘, 코드트리] 마법의 숲 탐색 - java

문제

문제가 상당히 길다. 전문을 보고 싶은 사람은 코드트리에서 확인하자.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

요약하자면 이렇다. 총 네 가지 동작을 수행해야 한다.

(1) 남쪽으로 한 칸 내려갑니다.

(2) (1)의 방법으로 이동할 수 없으면 서쪽 방향으로 회전하면서 내려갑니다. 이렇게 이동할 때 출구가 반시계방향으로 이동합니다.

(3) (1)과 (2)의 방법으로 이동할 수 없으면 동쪽 방향으로 회전하면서 내려갑니다. 이렇게 이동할 때 출구가 시계방향으로 이동합니다.

입력

첫 번째 줄에는 숲의 크기를 의미하는 R, C, 정령의 수 K가 공백을 사이에 두고 주어집니다.

그다음 줄부터 K개의 줄에 거쳐 각 골렘이 출발하는 열 ci​, 골렘의 출구 방향 정보 di​가 공백을 사이에 두고 주어집니다.

골렘의 출구 방향 정보 di​는 0과 3 사이의 수로 주어지며 각각의 숫자 0,1,2,3은 북, 동, 남, 서쪽을 의미합니다.

• 5≤R,C≤70
• 1≤K≤1000
• 2≤ci​≤C−1
• 0≤di​≤3

출력 형식

첫번째 줄에 각 정령들이 최종적으로 위치한 행의 총합을 출력하세요.

문제 풀이

이 문제 역시 지문을 천천히 잘 읽으면 어렵지 않게 구현해 낼 수 있다.

자료 구조 정의 및 입출력

static int R, C, K;
static int[][] map;
static int[] dc = {0,1,0,-1};
static int[] dr = {-1,0,1,0};

// 2차원 지도 초기화
init();
int result = 0;

while(K-- > 0) {
    st = new StringTokenizer(br.readLine());

    int c = Integer.parseInt(st.nextToken()) - 1;
    int r = 1;
    int d = Integer.parseInt(st.nextToken());

    // 골렘
    map[r][c] = d; // 센터에 출구 방향 표시
    map[r - 1][c] = 4;
    map[r + 1][c] = 4;
    map[r][c - 1] = 4;
    map[r][c + 1] = 4;

    boolean movedFlag = true;
    // 이번에 움직였으면 반복
    while(movedFlag) {
        movedFlag = false;
        // step 1
        if(check(r, c, 2)) {
            // move();
            
            // 바닥에 닿았으면 break;
            
            movedFlag = true;
        }
        // step 2
        else if (check(r, c, 3)) {{
            // move();
            movedFlag = true;
        }
        // step 3
        else if (check(r, c, 1)) {{
            // move();
            movedFlag = true;
        }
    }
    
    // 출구 표시
    d = map[r][c];
    int exitR = r + dr[d];
    int exitC = c + dc[d];
    map[exitR][exitC] = 5;
    
    // 골렘이 주어진 맵 밖에 있는지 확인
    if(isOutOfMap()) {
        init();
    } else {
    	// 정령이 움직일 수 있는 범위내에서 bfs 탐색
        result += bfs(r, c);
    }
}

System.out.println(result);

격자 형태의 지도 위에서 골렘과 정령이 움직이므로 map은 2차원 정수 배열로 선언한다. 움직일 방향에 대해서 dr, dc를 문제에서 주어진 순서(0 : 북, 1 : 동, 2 : 남, 3:서)로 선언한다.

2차원 지도 초기화 함수 _ init()

static private void init() {
    map = new int[R + 3][C];
    for(int[] line : map) {
        Arrays.fill(line, -1);
    }
}

기존의 2차원 지도 위에서 시작하는 문제가 아니라 '골렘이 지도에 들어오기 전'이라는 상태가 추가되었다. 따라서 골렘의 크기만큼 "지도 외의 지도"를 추가해줘야 한다.

골렘의 몸은 0~5까지 표현할 것이다. 골렘의 중앙(정령이 서있는 위치)에 0, 1, 2, 3으로 출구의 방향을 기록하고 골렘의 몸은 4, 골렘의 출구는 5로 기록한다. 따라서 아무것도 없는 격자는 -1을 가져야 한다.

d 방향으로 골렘이 움직일 수 있는가? _ check()

골렘이 d 방향으로 움직일 수 있는가 확인하기 위해서 dr, dc를 활용하는 함수를 작성한다.

static private boolean check(int r, int c, int direction) {
    // 주어진 방향(int direction)대로 중심 좌표를 옮겨준다.
    int nextR = r + dr[direction];
    int nextC = c + dc[direction];

    if(nextC - 1 < 0 || nextC + 1 >= C || nextR + 1 >= R + 3) {
        return false;
    }

    if(map[nextR][nextC + 1] >= 4 || map[nextR + 1][nextC] >= 4 || 
        map[nextR][nextC - 1] >= 4 || map[nextR - 1][nextC] >= 4) {

        return false;
    }

    if(direction == 3) {
        if(nextR + 2 >= R + 3) {
            return false;
        }
        else if(map[nextR + 1][nextC - 1] >= 4 || map[nextR + 2][nextC] >= 4) {
            return false;
        }
    } else if(direction == 1) {
        if(nextR + 2 >= R + 3) {
            return false;
        }
        else if(map[nextR + 1][nextC + 1] >= 4 || map[nextR + 2][nextC] >= 4) {
            return false;
        }
    }

    return true;
}

문제에서 조건으로 설명한 칸의 위치를 골렘의 중심 좌표를 기준으로 한 상대 좌표로 생각하여 조건식을 작성한다. 직접 해보면 어려울 것 없으므로 설명은 생략한다.

지도 위에 골렘을 움직이자 _ move()

/**
 * function main
 */
move(r, c, 2);
r += dr[2];
c += dc[2];

지도 위에서 골렘을 움직이는 move 함수를 만들 것이다. 단, move함수는 지도 위의 표현을 위해 작성했으므로 main에서 직접 골렘의 중심 좌표를 움직여줘야 한다.

static private void move(int r, int c, int direction) {
    // 출구 방향 기억
    int exit = map[r][c];

    // 지도 비우기
    map[r][c] = -1;
    map[r - 1][c] = -1;
    map[r + 1][c] = -1;
    map[r][c - 1] = -1;
    map[r][c + 1] = -1;

    // 옮기기
    int nextR = r + dr[direction];
    int nextC = c + dc[direction];

    map[nextR - 1][nextC] = 4;
    map[nextR + 1][nextC] = 4;
    map[nextR][nextC - 1] = 4;
    map[nextR][nextC + 1] = 4;

    // 출구 표시하기
    if(direction == 2) {
        map[nextR][nextC] = exit;
    }
    // 서쪽으로 회전하면서 내려가기(시계 반대방향)
    else if(direction == 3) {
        map[nextR][nextC] = (exit + 3) % 4;
    }
    // 동쪽으로 회전하면서 내려가기(시계 방향)
    else if(direction == 1) {
        map[nextR][nextC] = (exit + 1) % 4;
    }
}

지도 위에서 골렘의 좌표를 직접 옮겨준다. 이미 check함수에서 앞으로 나갈 수 있음을 계산했으므로 별도의 검증 함수는 필요 없다.

/**
 * function main
 */
// 출구 표시
d = map[r][c];
int exitR = r + dr[d];
int exitC = c + dc[d];
map[exitR][exitC] = 5;

메인 함수에서의 반복문을 통해 더 이상 골렘이 움직일 수 없을 때 골렘의 중앙에 기록한 골렘 출구의 방향으로 골렘의 출구를 5로 채워준다.

지도 외 구역에 골렘이 걸쳐있다면? _ isOutOfMap()

/**
 * function main
 */
if(isOutOfMap()) {
    init();
} else {
    result += bfs(r, c);
}

골렘이 지도 외 구역에 걸쳐있다면 결과에 반영하지 않고 지도를 초기화해야 한다.

static private boolean isOutOfMap() {
    for(int r = 0; r < 3; r++) {
        for(int c = 0; c < C; c++) {
            if(map[r][c] > 0) {
                return true;
            }
        }
    }
    return false;
}

정령이 갈 수 있는 곳은? _ bfs()

static private int bfs(int r, int c) {
    int max = Integer.MIN_VALUE;

    Queue<int[]> q = new ArrayDeque<>();
    boolean[][] visit = new boolean[R + 3][C];

    q.add(new int[] {r, c});
    visit[r][c] = true;
    while(!q.isEmpty()) {
        int[] now = q.poll();

        for(int d = 0; d < 4 ;d++) {
            int nextR = now[0] + dr[d];
            int nextC = now[1] + dc[d];

            if(nextC < 0 || nextC >= C || nextR < 0 || nextR >= R + 3) {
                continue;
            }
            if(visit[nextR][nextC]) {
                continue;
            }
            if(map[nextR][nextC] < 0) {
                continue;
            }
            // 현재 위치가 4면 다른 4, 5로 못 넘어감
            if(map[now[0]][now[1]] == 4 && map[nextR][nextC] >= 4) {
                continue;
            }

            q.add(new int[] {nextR, nextC});
            visit[nextR][nextC] = true;
            max = Math.max(max, nextR);
        }
    }

    return max - 2;
}

bfs로 정령이 갈 수 있는 지도의 가장 아래 좌표를 찾는다. 이때 bfs의 조건에 유의하자. 

(1) 지도를 벗어나면 안 된다
(2) 이미 방문한 곳은 안된다
(3) 골렘이 아닌 위치는 갈 수 없다
(4) 골렘의 몸에 서있다면(현재 값이 4이면) 다른 골렘으로 넘어갈 수 없다(4, 5로 갈 수 없다)

또한 bfs의 결과는 지도 외 구역에 의해서 2만큼 밀려나있다. 싱크를 맞춰주자.

전체 코드

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

public class Main {

    static int R, C, K;
    static int[][] map;
    static int[] dc = {0,1,0,-1};
    static int[] dr = {-1,0,1,0};

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

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        init();

        int result = 0;
        while(K-- > 0) {
            st = new StringTokenizer(br.readLine());

            int c = Integer.parseInt(st.nextToken()) - 1;
            int r = 1;
            int d = Integer.parseInt(st.nextToken());

            // 골렘
            map[r][c] = d; // 센터에 출구 방향 표시
            map[r - 1][c] = 4;
            map[r + 1][c] = 4;
            map[r][c - 1] = 4;
            map[r][c + 1] = 4;

            boolean movedFlag = true;
            // 이번에 움직였으면 반복
            while(movedFlag) {
                movedFlag = false;
                // step 1
                if(check(r, c, 2)) {
                    move(r, c, 2);
                    r += dr[2];
                    c += dc[2];

                    //바닥에 닿았으면 break;
                    if(r + 1 == R + 2) {
                        break;
                    }
                    movedFlag = true;
                }
                // step 2
                else if (check(r, c, 3)) {
                    move(r, c, 3);
                    r += dr[3];
                    c += dc[3];
                    movedFlag = true;
                }
                // step 3
                else if (check(r, c, 1)) {
                    move(r, c, 1);
                    r += dr[1];
                    c += dc[1];
                    movedFlag = true;
                }
            }
            // System.out.println("현재 골렘의 중앙 --- " + r + "   " + c + "   " + map[r][c]);
            // 출구 표시
            d = map[r][c];
            int exitR = r + dr[d];
            int exitC = c + dc[d];
            map[exitR][exitC] = 5;
            // System.out.println("현재 골렘의 출구 --- " + exitR + "   " + exitC);

            if(isOutOfMap()) {
                init();
            } else {
                result += bfs(r, c);
            }
        }
        System.out.println(result);
    }

    static private boolean check(int r, int c, int direction) {
        int nextR = r + dr[direction];
        int nextC = c + dc[direction];
        
        if(nextC - 1 < 0 || nextC + 1 >= C || nextR + 1 >= R + 3) {
            return false;
        }

        if(map[nextR][nextC + 1] >= 4 || map[nextR + 1][nextC] >= 4 || 
            map[nextR][nextC - 1] >= 4 || map[nextR - 1][nextC] >= 4) {

            return false;
        }

        if(direction == 3) {
            if(nextR + 2 >= R + 3) {
                return false;
            }
            else if(map[nextR + 1][nextC - 1] >= 4 || map[nextR + 2][nextC] >= 4) {
                return false;
            }
        } else if(direction == 1) {
            if(nextR + 2 >= R + 3) {
                return false;
            }
            else if(map[nextR + 1][nextC + 1] >= 4 || map[nextR + 2][nextC] >= 4) {
                return false;
            }
        }

        return true;
    }

    static private void move(int r, int c, int direction) {
        // 출구 방향 기억
        int exit = map[r][c];

        // 지도 비우기
        map[r][c] = -1;
        map[r - 1][c] = -1;
        map[r + 1][c] = -1;
        map[r][c - 1] = -1;
        map[r][c + 1] = -1;

        // 옮기기
        int nextR = r + dr[direction];
        int nextC = c + dc[direction];

        map[nextR - 1][nextC] = 4;
        map[nextR + 1][nextC] = 4;
        map[nextR][nextC - 1] = 4;
        map[nextR][nextC + 1] = 4;

        // 출구 표시하기
        if(direction == 2) {
            map[nextR][nextC] = exit;
        }
        // 서쪽으로 회전하면서 내려가기(시계 반대방향)
        else if(direction == 3) {
            map[nextR][nextC] = (exit + 3) % 4;
        }
        // 동쪽으로 회전하면서 내려가기(시계 방향)
        else if(direction == 1) {
            map[nextR][nextC] = (exit + 1) % 4;
        }
    }

    static private boolean isOutOfMap() {
        for(int r = 0; r < 3; r++) {
            for(int c = 0; c < C; c++) {
                if(map[r][c] > 0) {
                    return true;
                }
            }
        }
        return false;
    }

    static private void init() {
        map = new int[R + 3][C];
        for(int[] line : map) {
            Arrays.fill(line, -1);
        }
    }

    static private int bfs(int r, int c) {
        int max = Integer.MIN_VALUE;

        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visit = new boolean[R + 3][C];

        q.add(new int[] {r, c});
        visit[r][c] = true;
        while(!q.isEmpty()) {
            int[] now = q.poll();

            for(int d = 0; d < 4 ;d++) {
                int nextR = now[0] + dr[d];
                int nextC = now[1] + dc[d];

                if(nextC < 0 || nextC >= C || nextR < 0 || nextR >= R + 3) {
                    continue;
                }
                if(visit[nextR][nextC]) {
                    continue;
                }
                if(map[nextR][nextC] < 0) {
                    continue;
                }
                // 현재 위치가 4면 다른 4, 5로 못 넘어감
                if(map[now[0]][now[1]] == 4 && map[nextR][nextC] >= 4) {
                    continue;
                }

                q.add(new int[] {nextR, nextC});
                visit[nextR][nextC] = true;
                max = Math.max(max, nextR);
            }
        }

        return max - 2;
    }
}

풀이 소요 시간 : 1시간 30분