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

---

안녕하세요.
지금까지 계속 저만의 기술 블로그를 만들어야지, 만들거야
마음으로만 다짐하다가 인제야 시작하게 되었습니다.
비록 시작은 코딩일기지만, 그 끝은 창대하게
어엿한 개발자 블로그로 성장할 수 있도록 노력하겠습니다.

---

Prologue

안녕하세요!
나동빈 저자의 [이것이 코딩 테스트다] 문제풀이 정리 포스트입니다.

[게임 개발]

<문제>

현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 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가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.

  • 0 : 북쪽
  • 1 : 동쪽
  • 2 : 남쪽
  • 3 : 서쪽

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

  • 0 : 육지
  • 1 : 바다

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

<출력 조건>

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

<입력 예시>                                                                             <출력 예시>

• 4 4                                                                                           3
  1 1 0 // (1, 1)에 북쪽(0)을 바라보고 서 있는 캐릭터
  1 1 1 1
  1 0 0 1
  1 1 0 1
  1 1 1 1

---

PseudoCode

처음 문제를 봤을 때 들었던 생각은

1. 우선 맵을 담을 map[][]과 그 각 칸을 들렸는지의 여부를 체크할 visit[][]을 만들자

2. 캐릭터가 바라보는 방향 각각의 움직임을 셋팅하자

3. 생각대로 구현을 .. 잘하자 ..

입니다.

이런 문제들이 참 규칙도 상세하게 주고 이해 자체에는 문제가 없는데 구현을 하는데 있어서 꼬이면 답이 없더라구요 .. 이 문제도 좀처럼 잘 되지 안하서 하루 지난 다음 풀어보니 너무 쉽게 풀려서 상당히 허망감을 안겨준 문제였습니다 ㅠㅠ
그럼 코드를 보시죠.

---

SourceCode

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main
{
    static int[][] map;
    static boolean[][] visit;
    static int playerDir;
    static int playerRowPos;
    static int playerColPos;
    //북동남서를 바라볼때 움직이는 경로
    static int[] dRow = {-1, 0, 1, 0};
    static int[] dCol = {0, 1, 0, -1};

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

        int mapRow = Integer.parseInt(st.nextToken());
        int mapCol = Integer.parseInt(st.nextToken());

        map = new int[mapRow][mapCol];
        visit = new boolean[mapRow][mapCol];

        st = new StringTokenizer(br.readLine());
        playerRowPos = Integer.parseInt(st.nextToken());
        playerColPos = Integer.parseInt(st.nextToken());
        playerDir = Integer.parseInt(st.nextToken());

        visit[playerRowPos][playerColPos] = true;

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

        int count = 0;
        int visitCount = 1;

        while (true)
        {
            turnPlayer();

            if ((map[playerRowPos + dRow[playerDir]][playerColPos + dCol[playerDir]] == 0) &&
                    (visit[playerRowPos + dRow[playerDir]][playerColPos + dCol[playerDir]] == false))
            {
                visit[playerRowPos + dRow[playerDir]][playerColPos + dCol[playerDir]] = true;
                visitCount++;

                playerRowPos += dRow[playerDir];
                playerColPos += dCol[playerDir];

                count = 0;
            } else
            {
                count++;
            }

            if (count == 4)
            {
                if (map[playerRowPos - dRow[playerDir]][playerColPos - dCol[playerDir]] == 1)
                {
                    break;
                } else
                {
                    count = 0;
                    playerRowPos -= dRow[playerDir];
                    playerColPos -= dCol[playerDir];
                }

            }
        }

        System.out.println(visitCount);
    }

    static void turnPlayer()
    {
        playerDir -= 1;

        if (playerDir < 0)
        {
            playerDir = 3;
        }
    }
}

(언제나처럼 코드리뷰! 부탁드립니다!)

수도코드를 그대로 구현하였습니다. 말씀드렸다시피 문제 자체는 어렵지 않습니다. 다만, 구현에 집중해야할 뿐

코드를 살펴보면,

---

static int[][] map;
static boolean[][] visit;
static int playerDir;
static int playerRowPos;
static int playerColPos;
//북동남서를 바라볼때 움직이는 경로
static int[] dRow = {-1, 0, 1, 0};
static int[] dCol = {0, 1, 0, -1};

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

    int mapRow = Integer.parseInt(st.nextToken());
    int mapCol = Integer.parseInt(st.nextToken());

    map = new int[mapRow][mapCol];
    visit = new boolean[mapRow][mapCol];

    st = new StringTokenizer(br.readLine());
    playerRowPos = Integer.parseInt(st.nextToken());
    playerColPos = Integer.parseInt(st.nextToken());
    playerDir = Integer.parseInt(st.nextToken());

    visit[playerRowPos][playerColPos] = true;
    
    for (int i = 0; i < mapRow; i++)
    {
        st = new StringTokenizer(br.readLine());
        for (int j = 0; j < mapCol; j++)
        {
            map[i][j] = Integer.parseInt(st.nextToken());
        }
    }
    
    int count = 0;
    int visitCount = 1;

우선 필요한 변수들을 몇 가지 선언 및 초기화하는 파트입니다.
셋팅할게 많다보니 아무래도 코드가 조금 길어졌습니다.

• 게임의 맵을 담당하는 map[ ][ ]
• 각 칸의 방문 여부를 체크하는 visit[ ][ ]
• 캐릭터가 바라보는 방향 playerDir
• 캐릭터의 좌표값 playerRowPos, playerColPos
• 바라보는 방향의 각 움직임 dRow[ ], dCol[ ]
• 값을 입력받기 위한 BufferedReader
• 입력받은 값의 공백 처리를 위한 StringTokenizer
• 4번 회전 하였는지 점검을 위한 count
• 몇 칸을 방문했는지 세는 visitCount

우선 맵의 크기를 입력받아 맵을 만들고 그 크기만큼 방문 여부를 위한 visit[ ][ ]도 만들어 줍니다.
Java에서는 boolean 타입으로 만들었을때 초기값을 false로 해주니 이대로 사용하면 됩니다.

이런 문제를 풀때 캐릭터의 방향 전환 등 메소드를 따로 분리해서 작성하는 경우가 많기 때문에 메소드들이 공유할 수 있는 map[ ][ ]이나 visit[ ][ ] 등은 static 변수로 선언하면 관리하기 용이합니다. 대신 값이 메소드를 호출하면서 꼬이지 않게 잘 관리해줘야 합니다.

이런 문제를 풀때 dx[ ], dy[ ] 를 써왔는데 실제 좌표평면과 배열에서 x, y는 표현이 조금 달라서 문제를 푸는내내 이 부분이 헷갈렸습니다. 그래서 저는 x와 y가 아닌 row, col 의 개념으로 생각하기로 했고 따라서 변수명도 그에 맞게 수정하였습니다. 이게 저한테는 상상할때 헷갈리지도 않고 행렬의 개념으로 접근하니까 뭔가 자연스럽더라구요. 혹시 저처럼 x, y 좌표개념이 헷갈리신다면 이 방법도 해보시길 추천드립니다.

캐릭터가 바라볼때 방향이 문제에서 0, 1, 2, 3 이므로 각 상황을 인덱스에 넣으면 현재 캐릭터의 위치에서 연산하여 좌표값을 계산하는 식으로 움직이도록 구현하였습니다.

그리고 캐릭터가 놓였을 때에는 그 칸을 방문한 것이므로 바로 해당 칸의 visit[ ][ ]을 true 처리 하였습니다.

---

    while (true)
    {
        turnPlayer();

        if ((map[playerRowPos + dRow[playerDir]][playerColPos + dCol[playerDir]] == 0) &&
            (visit[playerRowPos + dRow[playerDir]][playerColPos + dCol[playerDir]] == false))
            {
                visit[playerRowPos + dRow[playerDir]][playerColPos + dCol[playerDir]] = true;
                visitCount++;

                playerRowPos += dRow[playerDir];
                playerColPos += dCol[playerDir];

                count = 0;
            }
        else
        {
            count++;
        }

        if (count == 4)
        {
            if (map[playerRowPos - dRow[playerDir]][playerColPos - dCol[playerDir]] == 1)
            {
                break;
            }
            else
            {
                count = 0;
                playerRowPos -= dRow[playerDir];
                playerColPos -= dCol[playerDir];
            }
        }
    }
    System.out.println(visitCount);
}

    static void turnPlayer()
    {
        playerDir -= 1;

        if (playerDir < 0)
        {
            playerDir = 3;
        }
    }
}

문제에 필요한 답을 찾는 실제로 캐릭터의 움직임을 구현하는 부분입니다.
사실 문제 자체는 어렵지 않습니다.

문제를 풀기 전에 먼저 바라보는 방향의 칸에 갈 수 없을 때 캐릭터의 방향을 도는 turnPlayer() 메소드를 따로 만들어 놓았습니다.

1. 캐릭터의 방향에 맞게 좌표를 계산한 다음 그 칸이 0 이거나 방문하지 않은 칸이면 방문하고 방문 횟수를 1 증가.

2. 앞으로 갈 수 없다면 캐릭터를 회전시키고 회전한 횟수를 1 증가 시킨다.

3. 회전한 횟수가 4라면 뒤로 갈 수 있는지 없는지 판단하는데 만약 갈 수 없으면 종료하고,
   갈 수 있다면 뒤로 가고 회전한 횟수를 0으로 초기화

이 부분은 큰 틀은 비슷하겠지만 푸는 사람의 노하우가 많이 녹아들 수 있는 부분이라서 이 정도의 설명으로 마무리 하겠습니다. (전 아직 노하우가 없어요 ㅠㅠ)

---

Epilogue

정말 알고리즘 문제를 완전 처음 접했을 때가 생각나네요. 그땐 저는 이런 문제를 못 풀거라고 굉장히 겁을 먹었는데 어느새 이렇게 문제도 풀어보고 풀어본 내용을 블로그에 정리하고 있는 지금을 생각해보니 감회가 새롭습니다. 이제는 이런 문제들을 계속 풀어봐서 실력을 늘려야 할 때인것 같습니다. 읽어주셔서 감사합니다!

코드에 대한 조언은 언제나 환영이며, 오히려 부탁드리겠습니다.