안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.
이번 포스팅은 백준 SW 기출문제 - 뱀 자바 풀이를 진행하고자 합니다.!
문제 출처: https://www.acmicpc.net/problem/3190
3190번: 뱀
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임
www.acmicpc.net
1. 풀이 소스:
import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = parseInt(br.readLine());
int K = parseInt(br.readLine());
Game game = new Game(N); // game 인스턴스 선언
StringTokenizer st;
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
game.setApple(parseInt(st.nextToken()), parseInt(st.nextToken())); // 사과 등록
}
int L = parseInt(br.readLine());
for (int i = 0; i < L; i++) {
st = new StringTokenizer(br.readLine());
game.addDirection(parseInt(st.nextToken()), st.nextToken()); // 시간에 맞춰 변경해야하는 시간과 방향 설정
}
System.out.println(game.run());
}
}
class Game {
int n;
int time; // 출력해야 하는 시간
boolean[][] nowVisited; // 현재 뱀의 몸(머리, 꼬리 포함)이 걸쳐 있는지 판단
boolean[][] map; // 사과 있는지 판단
char nowDir = 'R'; // 현재 방향 (계속 바뀜)
List<Tail> tails = new LinkedList<>(); // 꼬리 추가 및 삭제를 위한 링크드 리스트
Queue<Direction> dirs = new ArrayDeque<>(); // 시간에 맞춰 방향 변경을 위한 큐
Game (int n) {
this.n = n;
map = new boolean[n + 1][n + 1]; // n by n 이므로 n + 1로 초기화
nowVisited = new boolean[n + 1][n + 1];
}
void setApple(int row, int col) {
map[row][col] = true; // apple 설정
}
void addDirection(int ttl, String dir) {
dirs.add(new Direction(ttl, dir)); // 시간에 맞는 방향 설정
}
int run() {
int r = 1; // 행
int c = 1; // 열
tails.add(new Tail(r, c)); // 시작은 머리와 꼬리가 동일 하므로 꼬리에 추가
while (true) { // 반복
if (!dirs.isEmpty() && time == dirs.peek().ttl) { //비어 있지 않고 ttl와 같음
Direction nextDir = dirs.poll(); // 다음 방향을 위한 Direction 인스턴스 큐에서 빼기
if (nowDir == 'U') { // 각 방향에 맞춰 회전 후 방향 재조정
if (nextDir.dir.equals("L")) nowDir = 'L';
else nowDir = 'R';
}
else if(nowDir == 'D') {
if (nextDir.dir.equals("L")) nowDir = 'R';
else nowDir = 'L';
}
else if (nowDir == 'L') {
if (nextDir.dir.equals("L"))nowDir = 'D';
else nowDir = 'U';
}
else if (nowDir == 'R') {
if (nextDir.dir.equals("L")) nowDir = 'U';
else nowDir = 'D';
}
}
// 회전을 마친 경우 혹은 회전이 없는 경우 nowDir에 방향에 맞춰 움직이기 시작
switch (nowDir) {
case 'U':
r--;
break;
case 'D':
r++;
break;
case 'L':
c--;
break;
case 'R':
c++;
break;
}
if (!isValid(r, c)) { // 이동하려는 곳이 인덱스에 벗어나거나, 몸통이 있는 곳이라면 종료
time++; // 종료시간은 마지막 움직이는 경우도 포함이므로
break;
}
nowVisited[r][c] = true; // 머리가 방문한 곳 방문 추가
// 위치한 곳에 사과가 있는지 파악하기
if (!map[r][c]) { // 없다면 머리 증가 후 꼬리 제거
tails.add(new Tail(r, c)); // 머리 추가
Tail tail = tails.get(0); // 맨 마지막 꼬리 가져오기
nowVisited[tail.r][tail.c] = false; // 꼬리가 사라지므로 false
tails.remove(0); // 꼬리 제거
}
else {
tails.add(new Tail(r, c)); // 사과가 있다면 머리 위치 추가
map[r][c] = false; // 사과 제거하기
}
time++; // 모든 움직임이 끝났으므로 시간++
}
return time;
}
// 이미 몸체의 일부가 방문하고 있는 경우 종료
boolean isValid(int r, int c) { // 맵의 유효한 범위에 아직 방문하지 않은 곳이여야
return r > 0 && r <= n && c > 0 && c <= n && !nowVisited[r][c];
}
class Tail {
int r; // row
int c; // col
Tail (int r, int c) {
this.r = r;
this.c = c;
}
}
class Direction {
int ttl; // time to live
String dir; // 방향성
Direction (int ttl, String dir) {
this.ttl = ttl;
this.dir = dir;
}
}
}
2. 풀이 중점 사항
해당 문제는 뱀이 움직일 때, 사과가 있는지 없는지 여부에 따라 몸통의 길이가 달라집니다.
따라서, 다음의 의사코드를 바탕으로 문제를 해결해야 합니다.
- 현재의 위치에서 방향을 먼저 설정하기
- 각 방향대로 움직이되, 보드 밖을 벗어나는 곳으로 이동하거나 혹은 이동한 곳에 뱀의 몸통이 존재한다면 종료하기
- 만약 움직인 곳이 유효하다면,
- 사과가 있다면 사과를 지우고 머리를 tails 링크드리스트에 추가하기, 현재 머리가 있는 곳에 몸통 여부 true 표시하기
- 사과가 없다면, 머리를 tails 링크드 리스트에 추가하고, 머리가 있는 곳에 몸통 여부 표시하기, 꼬리는 머리가 움직이므로 있던 장소에 몸통 여부를 false로 표시하고, tails에서 remove(0) 하기
- 모든 움직임이 마쳤으므로 시간을 ++ 하고 다시 while루프로 돌아가기
한 문제에 큐, 링크드리스트, 클래스, 이차원 배열, 방향 전환 등을 경험할 수 있는 좋은 시간이었던 것 같습니다.
자세한 풀이는 모두 주석으로 처리하였습니다.!
이상으로 뱀 자바 풀이를 마치도록 하겠습니다.
감사합니다.!
'Algorithm' 카테고리의 다른 글
| [Algorithm] SW 기출문제 - 테트로미노(14500) 자바 풀이 (0) | 2023.05.05 |
|---|---|
| [Algorithm] SW 기출문제 - 주사위 굴리기(14499) 자바 풀이 (0) | 2023.05.05 |
| [Algorithm] SW 기출문제 - 2048 (Easy) 자바 풀이 (0) | 2023.05.04 |
| [Algorithm] SW 기출문제 - 구슬 탈출2 자바 풀이 (0) | 2023.05.04 |
| [Algorithm] 프로그래머스 - 표현 가능한 이진트리 자바 풀이 (0) | 2023.05.03 |
