안녕하세요.
지금까지 계속 저만의 기술 블로그를 만들어야지, 만들거야
마음으로만 다짐하다가 인제야 시작하게 되었습니다.
비록 시작은 코딩일기지만, 그 끝은 창대하게
어엿한 개발자 블로그로 성장할 수 있도록 노력하겠습니다.
Prologue
안녕하세요!
나동빈 저자의 [이것이 코딩 테스트다] 문제풀이 정리 포스트입니다.
[게임 개발]
<문제>
현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.
-
현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
-
캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
-
만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 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() 메소드를 따로 만들어 놓았습니다.
-
캐릭터의 방향에 맞게 좌표를 계산한 다음 그 칸이 0 이거나 방문하지 않은 칸이면 방문하고 방문 횟수를 1 증가.
-
앞으로 갈 수 없다면 캐릭터를 회전시키고 회전한 횟수를 1 증가 시킨다.
-
회전한 횟수가 4라면 뒤로 갈 수 있는지 없는지 판단하는데 만약 갈 수 없으면 종료하고,
갈 수 있다면 뒤로 가고 회전한 횟수를 0으로 초기화
이 부분은 큰 틀은 비슷하겠지만 푸는 사람의 노하우가 많이 녹아들 수 있는 부분이라서 이 정도의 설명으로 마무리 하겠습니다. (전 아직 노하우가 없어요 ㅠㅠ)
Epilogue
정말 알고리즘 문제를 완전 처음 접했을 때가 생각나네요. 그땐 저는 이런 문제를 못 풀거라고 굉장히 겁을 먹었는데 어느새 이렇게 문제도 풀어보고 풀어본 내용을 블로그에 정리하고 있는 지금을 생각해보니 감회가 새롭습니다. 이제는 이런 문제들을 계속 풀어봐서 실력을 늘려야 할 때인것 같습니다. 읽어주셔서 감사합니다!
코드에 대한 조언은 언제나 환영이며, 오히려 부탁드리겠습니다.
%20%E1%84%87%E1%85%A9%E1%86%A8%E1%84%89%E1%85%A1%E1%84%87%E1%85%A9%E1%86%AB%205.PNG)