이 문제는 삼성 SW 역량 테스트의 기출문제라고 한다. 알고리즘 문제를 자주 풀어보면 업무에도 도움이 될 것 같아 정기적으로 연습해보려고 한다.
물론 알고리즘 문제를 잘 푸는것이 실제 업무 능력과 직접 연결되지 않을 수 있다는 것도 알고 있다. 그러나 개발사고를 키우는 데에는 도움이 되지 않을까 싶다. 그리고 스펙처럼 꾸준히 쌓으면 좋을 것 같아 생각정리할 때 틈틈이 풀어볼까 한다.
백준 3190번 뱀 문제
'Dummy'라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)
다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
6
3
3 4
2 5
5 3
3
3 D
15 L
17 D9
문제분석
한 번쯤은 해봤을 뱀 또는 지렁이 게임이라고 보면 된다. 정해진 맵에서 해당 뱀의 움직임을 미리 정해 놓고 시뮬레이션했을 때 게임이 끝나는 시간을 구하는 문제다.
알고리즘 문제를 처음 풀어봐 입력 단계에서 해석이 잘 안 되어 애를 먹었었다. 문제를 내가 이해하기 쉬운 말로 변경해 보자면 아래와 같다.
1. 맵의 크기를 입력받는다.
2. 사과의 개수를 입력받는다. (N개라고 가정한다.)
3. 2번에서 입력받은 개수만큼 사과의 위치를 입력 받는다 (N번 반복해서 입력받음)
4. 뱀의 이동횟수를 입력받는다. (M번이라고 가정한다.)
5. 4번에서 입력받은 횟수만큼 뱀의 위치를 변경한다 (M번 반복해서 입력받음)
6. 뱀이 자신의 몸에 부딛히거나 맵에 부딛히면 게임이 종료되고 종료시간을 출력한다.
우선, 게임의 맵은 x, y좌표로 이루어진 평면 맵이 존재해야 한다. 즉, 행과 열로 이루어진 이차원 배열로 변수를 만들면 될 것 같다는 생각이 먼저 들었다.
2, 3번을 통해 입력받은 사과들을 앞서 생성한 이차원 배열에 표시해 놓으면 뱀의 머리가 해당 좌표에 도달했을때 사과를 먹은 판정을 할 수 있을 것이다.
4, 5번을 통해 입력 받은 뱀의 이동 액션은 이동하는 데 걸리는 시간과 뱀의 이동 방향(L, D)을 입력받아 입력받은 시간에 뱀이 이동방향을 변경하면 된다.
뱀의 몸을 Queue로 만들어 이동할 때마다 머리(가장 나중에 저장된 데이터) 위치를 저장하고, 이동한 위치에 사과가 있다면 Queue를 유지하고, 사과가 존재하지 않는다면 꼬리(가장 처음 저장된 데이터)를 poll(삭제)하여, 뱀의 이동로직을 작성하고자 생각했다.
마지막으로 맵에 부딪히거나 자기 자신에게 부딪힌다면 게임종료 되게 된다. 여기서 맵을 벗어나는 경우는 간단했지만 자기 자신을 판단하는 게 생각하기 너무 어려웠다.
결국 해당 부분에서 다른 사람들은 어떻게 풀었는지 검색해 보았다. 검색결과 2차원 배열로 되어있는 맵을 1차원 배열로 치환하여 해당 값을 Queue에 저장하는 방식을 많이 사용하고 있었다. 맵의 크기 * (Y나 X좌표) + (X나 Y좌표)로 사용하였는데 수식만 보고는 이해가 안 되어서 위 그림과 같이 그려보았다.
겹치지 않고 2차원 배열을 1차원 배열로 표현할 수 있었다! 해당 방법을 알게 되었으니, 다른 곳에서도 응용해서 사용할 수 있을 것 같다.
문제풀이
아래 코드는 위에 설명한 로직으로 Java언어를 사용해서 작성한 코드이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
// BufferedReader를 사용해 입력을 효율적으로 받기 위한 설정
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer str = null;
// 뱀의 이동 방향을 나타내는 배열 (상, 우, 하, 좌)
int[] movingX = { 1, 0, -1, 0 }; // x축에 대한 방향 (우, 상, 좌, 하)
int[] movingY = { 0, 1, 0, -1 }; // y축에 대한 방향 (우, 상, 좌, 하)
// 맵의 크기 (N x N)
int mapSize = Integer.parseInt(br.readLine());
// 사과의 개수
int apples = Integer.parseInt(br.readLine());
// 맵 배열을 생성하고 0으로 초기화 (사과가 있는 위치는 1로 표시됨)
int[][] map = new int[mapSize][mapSize];
// 뱀의 이동 정보 (시간, 방향)를 저장하는 HashMap
Map<Integer, String> moveInfoMap = new HashMap<>();
int a = 0;
int b = 0;
// 입력된 사과의 위치를 맵에 설정
for (int i = 0; i < apples; i++) {
str = new StringTokenizer(br.readLine());
a = Integer.parseInt(str.nextToken()) - 1; // 행 (0부터 시작하기 때문에 -1)
b = Integer.parseInt(str.nextToken()) - 1; // 열 (0부터 시작하기 때문에 -1)
map[a][b] = 1; // 사과가 있는 위치는 1로 표시
}
// 이동 정보 입력
int movingInfo = Integer.parseInt(br.readLine());
int movingTime = 0;
// 이동 시간과 방향을 moveInfo 맵에 저장
for (int i = 0; i < movingInfo; i++) {
str = new StringTokenizer(br.readLine());
movingTime = Integer.parseInt(str.nextToken()); // 방향 전환이 발생하는 시간
String direction = str.nextToken(); // 방향 전환 ("L" 또는 "D")
moveInfoMap.put(movingTime, direction); // 맵에 시간과 방향 저장
}
// 게임이 진행된 총 시간
int limitTime = 0;
// 현재 뱀의 머리 위치 (초기 위치는 (0,0))
int headX = 0, headY = 0;
// 다음으로 이동할 위치
int nextX = 0, nextY = 0;
// 뱀의 몸이 위치한 좌표를 큐에 저장 (초기에는 시작 위치만 포함)
Queue<Integer> bodyQ = new LinkedList<>();
bodyQ.add(0); // (0,0) 위치를 큐에 추가
// 뱀의 현재 머리이동 방향 (0 = 우, 1 = 상, 2 = 좌, 3 = 하)
int headPosition = 0;
// 게임 진행 루프
while (true) {
// 다음 위치 계산
nextX = headX + movingX[headPosition];
nextY = headY + movingY[headPosition];
limitTime++; // 시간 증가
// 벽에 부딪힌 경우 게임 종료
if (nextX < 0 || nextY < 0 || nextX >= mapSize || nextY >= mapSize) {
break;
}
// 몸통에 부딪힌 경우 게임 종료
// 큐에 현재 위치가 포함되어 있다면, 이는 뱀이 자신의 몸과 부딪혔다는 것을 의미
if (bodyQ.contains(nextY * mapSize + nextX)) {
break;
}
// 새로운 위치에 사과가 있는 경우
if (map[nextY][nextX] == 1) {
map[nextY][nextX] = 0; // 사과를 먹으면 사과 위치를 0으로 변경
bodyQ.add(nextY * mapSize + nextX); // 뱀의 새로운 위치를 큐에 추가 (길이 증가)
} else {
// 새로운 위치에 사과가 없는 경우
bodyQ.add(nextY * mapSize + nextX); // 뱀의 새로운 위치를 큐에 추가 (길이 증가)
bodyQ.poll(); // 뱀의 꼬리를 한 칸 줄여서 길이 유지(길이 감소)
}
// 현재 시간이 방향 전환 시간과 일치하면 방향을 전환
if (moveInfoMap.containsKey(limitTime)) {
String data = moveInfoMap.get(limitTime);
if (data.equals("D")) {
// 오른쪽 회전 (시계 방향)
headPosition += 1;
if (headPosition == 4) headPosition = 0; // 방향 배열의 인덱스 초과 방지
} else {
// 왼쪽 회전 (반시계 방향)
headPosition -= 1;
if (headPosition == -1) headPosition = 3; // 방향 배열의 인덱스 음수 방지
}
}
// 현재 머리 위치를 다음 위치로 업데이트
headX = nextX;
headY = nextY;
}
// 게임이 종료된 시점의 시간을 출력
System.out.println(limitTime);
}
}상세하게 주석을 달았으니, 쉽게 이해할 수 있을 것이다.
마무리
처음으로 알고리즘 문제를 풀어보았는데 코드를 작성하는 데에는 어려움이 없으나, 문제를 읽고 이해하는데 시간이 걸린 것 같다. 해당 문제를 통해 프로그래밍 사고가 더욱더 넓어진 것 같아 매우 재밌는 문제였다. 앞으로도 심심할 때 이런 재밌는 알고리즘 문제를 풀어봐야겠다고 생각했다.
이 글을 보는 선배님들 잘못된 정보나, 보완할 점이 있다면 댓글 달아주시면 감사하겠습니다 : )
'코딩테스트 > Java' 카테고리의 다른 글
| [백준 Beakjoon 1157번] 단어 공부 - 문제 해석 및 Java풀이 (0) | 2024.09.05 |
|---|---|
| [백준 Beakjoon 23971번] ZOAC 4 - 문제 해석 및 Java풀이 (2) | 2024.09.03 |
| [백준 Beakjoon 12865번] 평범한 배낭 - 문제 해석 및 Java풀이 (1) | 2024.08.28 |
