[코드트리/NOVICE MID] 작은 구슬의 이동 (JAVA)

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,1,-1,0};   // 🔔 동남북서 (행과 열 기준)
    static int[] dy = {1,0,0,-1};
 
    static int N, T, R, C;
    static char dir;
    static int[][] map;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());   // 격자 크기
        T = Integer.parseInt(st.nextToken());   // 시간
        map = new int[N + 1][N + 1];
 
        st = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        dir = st.nextToken().charAt(0);   // 방향
 
        int moveDir = getDir(dir);
        while(T --> 0) {
            int nx = R + dx[moveDir];
            int ny = C + dy[moveDir];
 
            if(!inRange(nx, ny)) {    // 격자 벗어나면 방향 전환
                moveDir = 3 - moveDir;
            }
            else {  // 이동
                R += dx[moveDir];
                C += dy[moveDir];
            }
        }
 
        System.out.println(R + " " + C);
    }
 
    // 이동 방향 가져오는 함수
    private static int getDir(char c) {
        if(c == 'R')    return 0;
        else if(c == 'D')   return 1;
        else if(c == 'U')   return 2;
        else                return 3;
    }
 
    // 범위 내에 있는지 확인하는 함수
    private static boolean inRange(int x, int y) {
        return (1 <= x && x <= N && 1 <= y && y <= N);
    }
}

 

 

 

🧩  해결 아이디어

• dx/dy techinque

1. 값들을 입력받는다.

2. 남은 시간만큼 이동 방향으로 이동하려 할 때 격자를 벗어나면, 방향을 전환하며 시간이 1초 소요된다. (moveDir = 3 - moveDir)

3. 격자를 벗어나지 않는다면, 이동 방향으로 이동하며 시간이 1초 소요된다.

 

- dx, dy 배열을 "행과 열로 생각"해 동남북서 순서로 저장한다.

- 방향 전환 시, 3에서 해당 방향을 뺸 값으로 바꾸면 방향 전환이 이뤄진다.

 

예를 들어 현재 이동 방향이 동쪽(0)인 상태로 격자 맨 끝에 닿았다고 할 때,

방향 전환하면 서쪽(3)이 되어야하므로 3-0 하는 것이다. 그러면 배열의 3번째 인덱스인 서쪽으로 방향이 전한된다.

 

 

---

🔺 다른 풀이들

- dx/dy 배열 값을 일반적으로(?) 생성해두시고,

격자 벗어나면 방향 전환을 dir  = (dir + 2) % 4;하고 continue;로 다음 차례로 돌아가게 했다.

static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};

.
.
.

int nx, ny;
for(int t = 0 ; t < T ; t++){
    nx = R + dx[dir];
    ny = C + dy[dir];

    if(!isRange(nx, ny)){	// 격자 벗어나면 방향 전환
        dir = (dir + 2) % 4;
        continue;
    }

    // 격자 내에 있으면 이동
    R = nx;
    C = ny;
}

 

---

💬 느낀 점

안 그래도 방향 전환하는 문제 잘 못 풀어서 언젠가 꼭 정리해야지 했는데 잘 만났다ㅠ

 

머릿속으로 뭔가 생각이 빨리 진행되지 않아서 구현까지도 시간이 오래 걸렸었다.

나는 평소 dx dy를 써야할 문제를 풀 때, dx dy를 행과 열 기준으로 생각하지 않고 동서남북 방향으로 생각했고

값을 고정시켜뒀었다.

그런데 이러면 방향 전환하고 이럴 때 뭔가 뇌정지가 와서 문제 해결까지 꽤 시간이 걸렸던 것이다...!! ㄴㅇㄱ

 

아예 행과 열로 생각해서 dx dy를 목적에 맞게 순서를 바꿔서 값을 설정해두고

이렇게 방향 전환하는 기술도 있구나 싶었다...

 

담엔 집중해서 더 빠르게 푸는 걸로!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리 dx/dy technique) 조건에 따라 방향이 변하는 경우