[코드트리] 마법의 숲 탐색

문제 링크

마법의 숲 탐색

풀이

히든케이스 때문에 어려웠던 문제. 실제로 시험장에서 풀었으면 통과하지 못했을 것 같다. 이 문제는 시뮬레이션이기는 하지만 골렘이 숲을 벗어난 경우를 처리하는 것이 매우 까다로웠다. 일일히 골렘이 숲을 벗어난 경우를 찾아서 예외 처리를 하기 보다는 그냥 배열의 세로 크기를 +3 해준 상태로 시뮬레이션을 돌렸다.

map = new int[R+3][C];

세로 인덱스 0 ~ 2는 숲 밖의 영역을 의미하게 된다.

if(y<=3) return false;

만약 정령의 위치가 0 ~ 3인 경우 골렘이 숲 밖에 있기 때문에 배열을 초기화하여 골렘을 밖으로 뺐다.

answer += center_move() - 2;

또한, 현재 위치를 더할 때도 본래 값에서 2를 빼줘야 한다.(3빼고 인덱스는 0부터 시작이므로 1을 더하기 때문)

나는 출구를 그냥 음수로 표현했다.

   1
1  1  1
  -1

위는 남쪽이 출구인 경우이다.

while(!q.isEmpty()){
  pos cur = q.poll();
  int num = map[cur.y][cur.x];
  max = Math.max(cur.y,max);
  for(int i=0;i<4;i++){
      int ny = dy[i]+cur.y, nx = dx[i]+cur.x;
      if(!(0<=ny && ny<R+3 && 0<=nx && nx<C)) continue;
      if(map[ny][nx] == 0 || visit[ny][nx]) continue; 
      if(num < 0 || map[ny][nx] == num || map[ny][nx] == - num){
          q.add(new pos(ny,nx));
          visit[ny][nx] = true;
      }
  }
}

이렇게 짜면 현재 정령의 위치가 음수인 경우에는 어디든 갈 수 있고(0 제외), 양수인 경우에는 자신과 같거나 자신의 값에 -1을 곱한 값에만 접근하는 조건으로 문제의 요구사항을 만족시킬 수 있다.

총 코드

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

public class Main {
    static int R,C,K;
    static int[][] map;
    static int cury, curx;
    static int[] dy = {-1,1,0,0}, dx = {0,0,-1,1};
    private static class pos{
        int y, x;
        pos(int y, int x){
            this.y = y;
            this.x = x;
        }
    }

    static void clean(int y, int x){
        map[y+1][x]= map[y-1][x]= map[y][x+1]= map[y][x-1]= map[y][x] = 0;
    }
    static boolean check(int y, int x){
        if(y+1 == R + 3 || x - 1 < 0 || x + 1 == C) return false; // 범위 밖으로 나가는 경우
        if(map[y+1][x]!=0 || map[y-1][x]!=0 || map[y][x+1]!=0 || map[y][x-1]!=0 || map[y][x]!=0) return false; // 다른 블록이 있는 경우
        return true;
    }

    static void move(int y,int x,int dir, int num){
        map[y+1][x]= map[y-1][x]= map[y][x+1]= map[y][x-1]= map[y][x] = num;
        if(dir == 0) map[y-1][x] = -num;
        else if(dir == 1) map[y][x+1] = -num;
        else if(dir == 2) map[y+1][x] = -num;
        else map[y][x-1] = -num;
    }

    public static boolean down(int ci, int dir, int num){
        int y = 1, x = ci;
        while(true){
            clean(y,x);
            if(check(y+1,x)){
                move(y+1,x,dir,num);
                y++;
            }
            else if(check(y,x-1) && check(y+1,x-1)){
                move(y+1,x-1,(dir+3)%4,num);
                y++;
                x--;
                dir = (dir+3)%4;
            }
            else if(check(y,x+1) && check(y+1,x+1)){
                move(y+1,x+1,(dir+1)%4,num);
                y++;
                x++;
                dir = (dir+1)%4;
            }else{
                move(y,x,dir,num);
                break;
            }
        }

        curx = x;
        cury = y;
        if(y<=3) return false;
        return true;
    }

    static int center_move(){
        Queue<pos> q = new LinkedList<>();
        q.add(new pos(cury,curx))
        boolean[][] visit = new boolean [R+3][C];
        visit[cury][curx] = true;
        int max = cury;
        
        while(!q.isEmpty()){
            pos cur = q.poll();
            int num = map[cur.y][cur.x];
            max = Math.max(cur.y,max);
            for(int i=0;i<4;i++){
                int ny = dy[i]+cur.y, nx = dx[i]+cur.x;
                if(!(0<=ny && ny<R+3 && 0<=nx && nx<C)) continue;
                if(map[ny][nx] == 0 || visit[ny][nx]) continue; 
                if(num < 0 || map[ny][nx] == num || map[ny][nx] == - num){
                    q.add(new pos(ny,nx));
                    visit[ny][nx] = true;
                }
            }
        }
        return max;
    }

    public static void main(String[] args) throws IOException {
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().trim().split(" ");
        R = Integer.parseInt(input[0]);
        C = Integer.parseInt(input[1]);
        K = Integer.parseInt(input[2]);
        map = new int[R+3][C];
        int answer = 0;
        for(int num=1;num<=K;num++){
            input = br.readLine().trim().split(" ");
            int ci = Integer.parseInt(input[0]) - 1;
            int di = Integer.parseInt(input[1]);
            if(!down(ci,di,num)){
                map = new int[R+3][C];
            }else answer += center_move() - 2;
        }
        System.out.println(answer);
    }
}