[이것이 코딩 테스트다] 게임 개발 (Java)

시간제한

1초

 

문제

현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다.

캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.

 

맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다.

캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.

캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.

 

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.

2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다.

왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

 

현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다.

매뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

 

입력

- 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3 <= N, M <= 50)

- 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다.

  방향 선의 값으로는 다음과 같이 4가지가 존재한다.(0: 북쪽 , 1: 동쪽 , 2: 남쪽 , 3: 서쪽)

- 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어 있다. (0: 육지 , 1: 바다)

- 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

입력 예시

4 4
1 1 0
1 1 1 1 
1 0 0 1
1 1 0 1
1 1 1 1

 

출력

첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

출력 예시

3

---

문제 풀이 과정

맵의 구조를 2차원 배열에 저장

 

int[][] map = new int[N][M];
for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < M; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
    }
}

세로 크기 N, 가로 크기 M만큼의 배열을 할당한 후 2중 for문을 통해 맵의 구조를 2차원 배열에 저장한다.

 

방향을 설정하는 dx, dy 배열 만들기

캐릭터는 상하좌우로 움직일 수 있다.

위의 조건에 따라 캐릭터는 북쪽, 동쪽, 남쪽, 서쪽으로 이동이 가능하다.

 

예를 들어 조금 더 상세히 살펴보면

현재 캐릭터의 위치 (1, 1)

북쪽으로 이동한 경우: (0, 1) -> 행 -1

동쪽으로 이동한 경우: (1, 2) -> 열  +1

남쪽으로 이동한 경우: (2, 1) -> 행 +1

서쪽으로 이동한 경우: (1, 0) -> 열 -1

이렇게 행(x), 열(y)의 좌표가 변하는 것을 알 수 있다.

 

이를 통하여 dx, dy배열을 만든다.

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

 

캐릭터 매뉴얼 분석

매뉴얼을 차근차근 코드로 구현해 보자.

 

1단계

현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.

입력 값을 받으면 캐릭터의 방향을 알 수 있다. 해당 방향을 기준으로 왼쪽으로 회전한다.

 

만약 캐릭터의 방향이 북쪽인 경우, 북 -> 서 -> 남 -> 동 -> 북으로 회전한다.

해당 방향의 값과 함께 보면 0 -> 3 -> 2 -> 1 -> 0이 된다.

규칙을 찾아보면 d가 0인 경우는 3이 되고 이를 제외한 경우는 d - 1이다. 

d -= 1;
if (d == -1) {
    d = 3;
}

 

2단계

캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

이제는 캐릭터의 방향대로 앞으로 한 칸 나아가볼 차례이다.

조건에 따르면 육지인 아직 가보지 않은 칸만 캐릭터는 전진할 수 있다.

 

위에서 구현한 dx, dy배열을 활용하여 다음 x, y좌표를 구한다.

int nx = A + dx[d];
int ny = B + dy[d];

 

최종 출력 값은 캐릭터가 방문한 칸의 수이다.

처음 캐릭터가 서있던 칸은 반드시 방문하게 되므로 moveCount를 1로 초기화한다.

또한 캐릭터는 가보지 않은 칸만 전진할 수 있으므로 처음 칸은 -1로 따로 체크한다.

int moveCount = 1;
map[A][B] = -1;

 

map에서 캐릭터가 방문한 경우는 -1이고 바다인 경우는 1이므로 다음 칸의 값이 0인 경우가 "육지인 아직 가보지 않은 칸"이 된다.

해당 칸에 전진한 경우 그 칸을 -1로 방문처리 한 후 현재 캐릭터의 좌표로 바꾼다.

캐릭터는 새로운 칸을 방문했으므로 moveCount의 값은 1 증가시킨다.

while (true) {
    if (map[nx][ny] == 0) {
        map[nx][ny] = -1;
        A = nx;
        B = ny;
        moveCount++;
        continue;
    }
 }

 

3단계

만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

캐릭터의 상하좌우 네 방향 모두 전진할 수 없는 경우, 한 칸 뒤로 이동해야 한다.

- 뒷 칸이 육지인 경우: 1단계로 돌아감

- 뒷 칸이 바다인 경우: 움직임을 멈춘다(종료)

 

먼저 3단계를 구현하기 위해서는 캐릭터의 회전 개수를 체크해야 한다.

반복문을 돌면서 turnCount의 값을 1씩 증가시킨다.

int turnCount = 0;

while (true) {
    turnCount++;
    turnLeft();
}

 

명심할 것!!

다음 칸으로 전진한 경우에는 turnCount의 값을 0으로 초기화시킨다.

while (true) {
    if (map[nx][ny] == 0) {
        map[nx][ny] = -1;
        A = nx;
        B = ny;
        moveCount++;
        turnCount = 0;
        continue;
    }
 }

 

이제 turnCount의 값이 4가 되는 경우를 구현한다.

바라보는 방향으로 한 칸 앞으로 갈 때는 "+"로 한 칸 뒤로 갈 때는 "-"로 표현했다. 

 

해당 칸이 바다인 경우에는 while문을 종료하고 바다가 아닌 경우에는 현재 캐릭터의 좌표를 변경한 후 turnCount의 값을 0으로 초기화하여 다시 1단계로 돌아간다.

if (turnCount == 4) {
    nx = A - dx[d];
    ny = B - dy[d];

    if (map[nx][ny] == 1) {
        break;
    }
    A = nx;
    B = ny;
    turnCount = 0;
}

---

구현 코드

public class TC_4_2 {
    static int d;

    // 왼쪽 방향으로 회전
    static void turnLeft() {
        d -= 1;
        if (d == -1) {
            d = 3;
        }
    }

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        // 맵 배열에 저장
        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

        // 처음 있었던 곳 방문한 칸으로 체크
        map[A][B] = -1;

        while (true) {
            turnCount++;

            turnLeft();

            int nx = A + dx[d];
            int ny = B + dy[d];

            // 육지이면서 방문하지 않은 칸인 경우
            if (map[nx][ny] == 0) {
                map[nx][ny] = -1;
                A = nx;
                B = ny;
                moveCount++;
                turnCount = 0;
                continue;
            }

            // 네 방향 모두 확인
            if (turnCount == 4) {
                nx = A - dx[d];
                ny = B - dy[d];

                // 한 칸 뒤가 바다인 경우
                if (map[nx][ny] == 1) {
                    break;
                }
                A = nx;
                B = ny;
                turnCount = 0;
            }
        }
        System.out.println(moveCount);
    }
}

 

 

Reference

이것이 취업을 위한 코딩테스트다 - 나동빈