[BOJ] ๋ฑ€(3190)

[๋ฐฑ์ค€(BOJ)] 3190_๋ฑ€ JAVA

๋ฌธ์ œ : BOJ_3190๋ฒˆ ๋ฑ€

๋ฌธ์ œ ์„ค๋ช…

๋งค์ดˆ ์›€์ง์ด๋ฉด์„œ ๊ผฌ๋ฆฌ๋ฅผ ๋Š˜๋ ค๊ฐ€๋Š” ๋ฑ€ ๊ฒŒ์ž„์„ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
N*N ํฌ๊ธฐ์˜ ๋งต์ด ์ฃผ์–ด์ง€๊ณ , ์‚ฌ๊ณผ๊ฐ€ ์žˆ๋Š” ๊ฐ๊ฐ์˜ ์œ„์น˜์™€ ๋ฑ€์ด ๋ฐฉํ–ฅ์„ ๋ฐ”๊พธ๋Š” ์ˆœ๊ฐ„์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.
์ด๋•Œ ๋ฑ€์ด ์›€์ง์ธ ๋ฐฉํ–ฅ์— ์‚ฌ๊ณผ๊ฐ€ ์žˆ๋‹ค๋ฉด ์‚ฌ๊ณผ๋ฅผ ๋จน๊ณ  ๊ผฌ๋ฆฌ๊ฐ€ ๋Š˜์–ด๋‚˜์ง€๋งŒ, ์‚ฌ๊ณผ๊ฐ€ ์—†๋‹ค๋ฉด ๊ธฐ์กด์˜ ๊ผฌ๋ฆฌ ๋ถ€๋ถ„์ด ์‚ฌ๋ผ์ง€๊ณ  ๋ฑ€์˜ ๋จธ๋ฆฌ ๋ถ€๋ถ„์ด ๋Š˜์–ด๋‚ฉ๋‹ˆ๋‹ค.
๋˜ํ•œ ๋ฐฉํ–ฅ์€ ์ตœ์ดˆ์— ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ด๋™ํ•˜๋ฉฐ ์ด๋™๋ฐฉํ–ฅ์„ ๊ธฐ์ค€์œผ๋กœ ์˜ค๋ฅธ์ชฝ์ด๋‚˜ ์™ผ์ชฝ์œผ๋กœ 90๋„ ํšŒ์ „ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


Solution

๊ตฌํ˜„

๋ฌธ์ œ์—์„œ ์ฃผ์–ด์ง„ ๋Œ€๋กœ ๊ตฌํ˜„์„ ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.
๋ฑ€์˜ ํ˜„์žฌ ๋จธ๋ฆฌ ์œ„์น˜์™€ ๊ผฌ๋ฆฌ ์œ„์น˜๋ฅผ ๊ณ„์† ๊ธฐ๋กํ•ด ์ฃผ๋ฉด์„œ, ์ด๋™ํ•œ ๊ณณ์— ์‚ฌ๊ณผ๊ฐ€ ์žˆ์œผ๋ฉด ๋จธ๋ฆฌ ์œ„์น˜๋งŒ ์ˆ˜์ •ํ•ด ์ฃผ๊ณ , ์‚ฌ๊ณผ๊ฐ€ ์—†์„ ์‹œ์—” ๊ผฌ๋ฆฌ ์œ„์น˜๋„ ํ•จ๊ป˜ ์ˆ˜์ •ํ•ด ์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค.
์ด๋•Œ ๊ผฌ๋ฆฌ ์œ„์น˜๋งˆ๋‹ค ์–ด๋Š ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ–ˆ๋Š”์ง€๋„ ๊ธฐ๋กํ•ด ์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.(lastMove)
๋˜ํ•œ ๊ผฌ๋ฆฌ ์œ„์น˜๊ฐ€ ๋ฐ”๋€๋‹ค๋ฉด ๋งˆ์ง€๋ง‰ ๊ผฌ๋ฆฌ ์œ„์น˜์—๋Š” ๋ฑ€์ด ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒƒ์ด๋ฏ€๋กœ ๋นˆ ๊ณต๊ฐ„์œผ๋กœ ์ˆ˜์ •ํ•ด ์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
์ด๋•Œ ๋ฑ€์ด ์กด์žฌํ•œ๋‹ค๊ณ  ์ฒดํฌํ•œ ๋ถ€๋ถ„์œผ๋กœ ์ด๋™ํ•˜๊ฑฐ๋‚˜, ์ง€๋„ ๋ฐ–์œผ๋กœ ๋ฒ—์–ด๋‚˜๋Š” ์ˆœ๊ฐ„์„ ์ •๋‹ต์œผ๋กœ ์ถœ๋ ฅํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.


Description

  • dx[], dy[] ๋ฐฐ์—ด์„ ํ†ตํ•ด ์ด๋™๋ฐฉํ–ฅ์„ ์ •ํ•  ๋•Œ, ๋ฐฐ์—ด์˜ ๊ฐ’์—์„œ +1์ผ ์‹œ์—๋Š” ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํšŒ์ „, -1์ผ ์‹œ์—๋Š” ์™ผ์ชฝ์œผ๋กœ ํšŒ์ „ํ•˜๊ฒŒ ์ขŒํ‘œ๊ฐ’์„ ์ง€์ •ํ•ด ์ฃผ์—ˆ์Šต๋‹ˆ๋‹ค.
  • ๋ฑ€์˜ ๋ฐฉํ–ฅ ์ •๋ณด์—์„œ ์‹œ๊ฐ„์ธ X๋Š” X ์ดˆ์— ๋ฐฉํ–ฅ์„ ํšŒ์ „์‹œํ‚ค๋Š” ๊ฒŒ ์•„๋‹Œ X ์ดˆ๊ฐ€ ๋๋‚œ ๋’ค์— ๋ฐฉํ–ฅ์„ ์ „ํ™˜ํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.(result==moveCnt+1)

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair{
    private int cnt;
    private String direction;

    Pair(int cnt, String direction){
        this.cnt = cnt;
        this.direction = direction;
    }

    public int getCnt() {
        return cnt;
    }

    public String getDirection() {
        return direction;
    }
}

public class Main {

    public static int[][] map;
    public static int[][] lastMove;
    public static int[] dx = {0,1,0,-1};
    public static int[] dy = {1,0,-1,0};
    public static int dir = 0;

    public static int changeDir(int dir, String command){
        if(command.equals("L")){
            if(dir==0) return 3;
            else return dir-1;
        }
        else {
            if(dir==3) return 0;
            else return dir+1;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        map = new int[n+1][n+1];
        lastMove = new int[n+1][n+1];
        st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            map[x][y] = 2;
        }

        Queue<Pair> q = new LinkedList<>();

        st = new StringTokenizer(br.readLine());
        int l = Integer.parseInt(st.nextToken());
        for(int i=0;i<l;i++){
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            String direction = st.nextToken();
            q.offer(new Pair(cnt,direction));
        }

        dir = 0;
        int result = 0;
        map[1][1] = 1;
        lastMove[1][1] = dir;
        int nowX = 1;
        int nowY = 1;
        int endX = 1;
        int endY = 1;
        int moveCnt = 0;
        String moveDir = "";
        if(!q.isEmpty()) {
            moveCnt = q.peek().getCnt();
            moveDir = q.peek().getDirection();
        }
        while(true){
            result++;
            if(result==moveCnt+1){
                q.poll();
                dir = changeDir(dir,moveDir);
                if(!q.isEmpty()) {
                    moveCnt = q.peek().getCnt();
                    moveDir = q.peek().getDirection();
                }
            }
            int nextX = nowX + dx[dir];
            int nextY = nowY + dy[dir];
            if(nextX<=0 || nextY<=0 || nextX > n || nextY > n) break;
            if(map[nextX][nextY]==1) break;
            lastMove[nowX][nowY] = dir;
            nowX = nextX;
            nowY = nextY;
            if(map[nextX][nextY]==2){
                map[nextX][nextY] = 1;
                continue;
            }
            else {
                map[nextX][nextY] = 1;
                map[endX][endY] = 0;
                int nowDir= lastMove[endX][endY];
                endX += dx[nowDir];
                endY += dy[nowDir];
            }
        }
        bw.write(String.valueOf(result));
        bw.flush();
        br.close();
        bw.close();
    }

}