문제
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
코드
import java.io.*;
import java.util.*;
class Main {
public static class Location {
int row;
int column;
public Location(int row, int column) {
this.row = row;
this.column = column;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Location location = (Location) o;
return row == location.row && column == location.column;
}
}
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
boolean[][] map = new boolean[n][n];
for (int i = 0; i < k; i++) {
String s = br.readLine();
StringTokenizer st = new StringTokenizer(s);
map[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = true;
}
int l = Integer.parseInt(br.readLine());
char[] rotate = new char[10001];
for (int i = 0; i < l; i++) {
String s = br.readLine();
StringTokenizer st = new StringTokenizer(s);
rotate[Integer.parseInt(st.nextToken())] = st.nextToken().charAt(0);
}
LinkedList<Location> snake = new LinkedList<>();
snake.add(new Location(0, 0));
int state = 0;
int count = 0;
while (true) {
Location current = snake.getFirst();
switch (state) {
case 0:
snake.addFirst(new Location(current.row, current.column + 1));
break;
case 1:
snake.addFirst(new Location(current.row + 1, current.column));
break;
case 2:
snake.addFirst(new Location(current.row, current.column - 1));
break;
case 3:
snake.addFirst(new Location(current.row - 1, current.column));
break;
}
current = snake.getFirst();
if (current.row < 0 || current.row == n || current.column < 0 || current.column == n) {
count++;
break;
}
Iterator<Location> temp = snake.iterator();
temp.next();
while (temp.hasNext())
if (current.equals(temp.next())) {
bw.write(count + 1 + "\n");
bw.flush();
return;
}
if (!map[current.row][current.column])
snake.removeLast();
else
map[current.row][current.column] = false;
if (rotate[++count] == 'D')
state = (state + 1) % 4;
else if (rotate[count] == 'L')
state = (4 + state - 1) % 4;
}
bw.write(count + "\n");
bw.flush();
}
}다시 풀기(2023.01.08)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//N, K를 입력받고
int n = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
//그래프를 생성한 후 과일을 그래프에 1로 표시
int[][] graph=new int[n][n];
for(int i=0; i<k; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
graph[row-1][col-1]=1;
}
//L을 입력 받고
int l = Integer.parseInt(br.readLine());
//시간을 Key, 방향 전환을 Value로 저장
Map<Integer, String> change = new HashMap<>();
for(int i=0; i<l; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
change.put(Integer.parseInt(st.nextToken()), st.nextToken());
}
//꼬리는 순서대로 연결 리스트에 저장(삭제하기 위해)
LinkedList<int[]> tails = new LinkedList<>();
tails.add(new int[]{0, 0});
//현재의 방향과 방향 정보 배열 초기화
int direction=0;
int[][] directions=new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
//큐를 사용해서 진행할 것이므로 (0,0)을 넣고, (0,0)은 뱀의 몸통이 있다는 뜻으로 -1 표시
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0, 0});
graph[0][0]=-1;
int time=0;
while(!q.isEmpty()){
//1초 증가
time++;
//현재의 위치
int[] current = q.poll();
//다음에 갈 위치
int dx=directions[direction][0]+current[0];
int dy=directions[direction][1]+current[1];
//벽에 닿거나 몸통에 닿으면 끝
if(dx<0 || dy<0 || dx>=n || dy>=n || graph[dx][dy]==-1)
break;
//다음 위치에 과일이 없으면 꼬리를 제거해준다
if(graph[dx][dy]!=1){
int[] tail=tails.removeFirst();
graph[tail[0]][tail[1]]=0;
}
//다음 위치에 뱀의 머리가 있으므로 -1 표시
graph[dx][dy]=-1;
//방향 전환해야 할 시간이라면 전환
if(change.containsKey(time)){
if(change.get(time).equals("L"))
direction=(direction+3)%4;
else
direction=(direction+1)%4;
}
//큐에 다음 위치를 넣고, 꼬리 목록에 다음 위치 추가
q.add(new int[]{dx, dy});
tails.add(new int[]{dx, dy});
}
System.out.println(time);
}
}해결 과정
-
뱀의 몸 한 칸 한 칸마다 row와 column을 가진 노드를 LinkedList를 사용해서 뱀을 만들었다. 전체 map에서 사과가 있는 칸은 true로 해둬서 꼬리 노드를 삭제할 지 유지할 지 체크해주고, state 변수를 둬서 다음 머리의 위치를 정해준다. 벽을 넘었는지 확인하기 위해서 n과 뱀 머리 노드의 row, column을 비교해주고, 자신의 몸에 부딪혔는지 확인하기 위해서 Iterator를 사용해서 노드 하나 하나 선형 탐색해줬다.
-
😁
渽晛