문제
BOJ 3190: 뱀 https://www.acmicpc.net/problem/3190
풀이
조건
- 뱀이 이동한다.
- 머리가 먼저 이동한다.
- 이동한 자리에 사과가 없다면 꼬리를 한 칸 당겨 뱀 길이가 일정해 지도록 한다.
- 이동한 자리에 사과가 있다면 꼬리를 그대로 두어 뱀 길이가 한 칸 길어지도록 한다.
- 뱀의 머리가
영역 밖으로 벗어나거나자신의 몸에 닿이게되면 종료한다. - 뱀의
초기 위치는 (1, 1)이고초기 방향은 오른쪽이다.
풀이 순서
- 좌표와 헷갈리지 않게 하기 위해 map 크기를 N+1로 해준다.
- 사과의 위치에는 9를 넣어 준다.
HashMap을 이용하여Key 값에 시간,Value 값에 방향값을 넣어준다.- 시간에 따라
while문이 돌도록 해주고 반복 1회가 1초 동안 일어나는 일이다. - 뱀의 머리가 방향에 맞춰 이동을 한다.
- 뱀의 머리가
종료 조건에 해당하면 종료시킨다. - 뱀의 머리가 사과 위치로 왔다면 머리만 늘린다.
- 뱀의 머리가 빈 칸으로 왔다면 머리를 늘리고 꼬리는 줄어들게한다.
- 뱀의 머리가
현재 시간을 Key 값으로 하는Value 값이 있는지 확인하고 있다면해당 Value 값을 방향으로 갱신해준다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int N; // 맵 크기
static int K; // 사과 갯수
static int L; // 명령 갯수
static int time; // 답으로 낼 횟수
static int[][] map;
static ArrayList<int[]> snake; // 뱀의 몸통 좌표가 들어갈 리스트
static int idx = 0; // 방향 찾을 때 쓸 인덱스 -> 처음엔 오른쪽을 보고 있음
static int[] dx = {0, 1, 0, -1}; // 오른쪽 , 아래, 왼쪽, 윗쪽
static int[] dy = {1, 0, -1, 0};
static HashMap<Integer, Character> dir; // 이동 횟수와 방향 정보 넣을 맵
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine()); // 맵 크기
map = new int[N+1][N+1]; // 좌표값 안 헷갈리기 위해 N+1 해줌
K = Integer.parseInt(br.readLine()); // 사과 갯수
for(int i=0; i<K; i++) {
st = new StringTokenizer(br.readLine(), " ");
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
map[r][c] = 9; // 사과 위치
}
// 뱀 방향 정보 입력
dir = new HashMap<>(); // 이동 횟수와 방향 정보 넣을 맵
L = Integer.parseInt(br.readLine());
for(int i=0; i<L; i++) {
st = new StringTokenizer(br.readLine(), " ");
int moveCnt = Integer.parseInt(st.nextToken()); // 이동 횟수
char turnDir = st.nextToken().charAt(0); // 방향 정보
dir.put(moveCnt, turnDir);
}
// 뱀 시작
snake = new ArrayList<>(); // 뱀 몸통 넣을 리스트
snake.add(new int[] {1, 1}); // 처음엔 (1, 1)위치에 있기 때문에 넣어줌
time = 0;
int nx, ny; // 새롭게 이동한 위치
int thisX, thisY; // 현재 위치
thisX = 1;
thisY = 1;
while(true) {
time++; // 반복문이 반복 되는 것이 수행한 횟수
nx = thisX + dx[idx]; // 바라보는 방향으로 머리 좌표 이동
ny = thisY + dy[idx]; // 바라보는 방향으로 머리 좌표 이동
if(isFinish(nx, ny)) break; // 종료 조건이 되면 while문 탈출
// 사과를 만나면
if(map[nx][ny] == 9) {
map[nx][ny] = 0; // 사과 자리는 0으로 바꿔줌
snake.add(new int[] {nx, ny}); // 뱀 머리만 넣어줌
}
// 사과가 없는 자리라면
else {
snake.add(new int[] {nx, ny}); // 벰 머리 넣어줌
snake.remove(0); // 꼬리는 없애서 몸 길이를 일정하게 유지해 줌
}
thisX = nx; // 현재 위치 갱신
thisY = ny; // 현재 위치 갱신
// 현재 time을 key값으로 가진 값이 존재한다면
if(dir.containsKey(time)) {
// 해당 key 값의 value가 D라면
if(dir.get(time) == 'D') {
idx++;
if(idx == 4) idx = 0;
}
// 해당 key 값의 value가 L이라면
if(dir.get(time) == 'L') {
idx--;
if(idx == -1) idx = 3;
}
}
}
System.out.println(time);
}
// 끝나는 조건이면 true 반환
static boolean isFinish(int x, int y) {
// map 범위 벗어났는지 체크
if(x < 1 || y < 1 || x > N || y > N) return true;
// 뱀의 몸통과 머리가 만났는지 체크
for(int i=0; i<snake.size(); i++) {
if(x == snake.get(i)[0] && y == snake.get(i)[1]) {
return true;
}
}
return false;
}
}처음에 했던 틀린 풀이
풀이 순서
뱀의 몸이 있는 칸은1을 넣어준다.- 뱀의 머리가 새롭게 도달한 위치에 1을 넣어준다.
- 해당 위치에 사과가 있었다면 꼬리를 줄여주지 않는다.
- 해당 위치에 사과가 없었다면 꼬리를 줄여준다.
- 이 때
꼬리의 다음 위치가뱀의 몸인 1이 아니라면방향을 머리의 방향과 맞춰주고 이동시킨다. 꼬리의 다음 위치가뱀의 몸인 1이라면해당 방향으로꼬리를 당겨주고원래 있었던 꼬리의 위치에는 0을 넣어준다.
- 이 때
코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int ans; // 답
static int[][] map;
static char headDir, tailDir; // 머리와 꼬리의 방향
static int headX, headY;
static int tailX, tailY;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine()); // 보드 크기
map = new int[N][N];
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
map[i][j] = 0;
}
}
map[0][0] = 1; // 뱀의 초기 위치 -> 뱀이 있는 위치에는 1을 넣어줌
int K = Integer.parseInt(br.readLine()); // 사과 갯수
for(int i=0; i<K; i++) {
st = new StringTokenizer(br.readLine(), " ");
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
map[r-1][c-1] = 9; // 사과 위치
}
int L = Integer.parseInt(br.readLine()); // 뱀의 방향 전환 횟수
headDir = 'E'; // 머리의 초기 방향
tailDir = 'E'; // 꼬리의 초기 방향
// 머리의 초기 위치
headX = 0;
headY = 0;
// 꼬리의 초기 위치
tailX = 0;
tailY = 0;
for(int i=0; i<L; i++) {
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken()); // 게임 시작 후 x초
char c = st.nextToken().charAt(0); // 회전 방향
// 직진 횟수 만큼 반복
for(int j=0; j<x; j++) {
ans++;
// 머리가 앞으로 한 칸 감
headMove(headDir);
// 종료 조건 -> 범위를 벗어나거나 머리가 몸에 닿임
if(headX < 0 || headY < 0 || headX >= N || headY >= N || map[headX][headY] == 1) {
System.out.println(ans);
return;
}
// 앞으로 간 머리가 사과를 만나면
if(map[headX][headY] == 9) {
// 사과 자리를 1로 바꾸고 꼬리는 움직이지 않고 다음 반복문으로 넘김
map[headX][headY] = 1;
continue;
} else { // 앞으로 간 머리가 그냥 빈 칸 일 때
// 해당 자리에 1을 넣음
map[headX][headY] = 1;
// 꼬리가 있었던 자리는 0으로 바꿈
map[tailX][tailY] = 0;
// 꼬리가 몸 따라서 잘 가는지 체크
if(!checkNextTail(tailDir, tailX, tailY)) {
// 꼬리의 방향을 머리의 방향과 맞춰줌
tailDir = headDir;
}
// 꼬리 한 칸 움직임
tailMove(tailDir);
}
}
// 머리 방향 바꾸는 명령
headDir = changeDir(headDir, c);
}
}
// 머리의 방향대로 이동
static void headMove(char nowDir) {
switch(nowDir) {
case 'E': headY++;
break;
case 'S': headX++;
break;
case 'W': headY--;
break;
case 'N': headX--;
break;
default:
break;
}
}
// 꼬리의 방향대로 이동
static void tailMove(char nowDir) {
switch(nowDir) {
case 'E': tailY++;
break;
case 'S': tailX++;
break;
case 'W': tailY--;
break;
case 'N': tailX--;
break;
default:
break;
}
}
// 꼬리의 방향과 머리의 방향이 같다면 true 반환
static boolean checkNextTail(char tailDir, int nowTailX, int nowTailY) {
switch(tailDir) {
case 'E': nowTailY++;
break;
case 'S': nowTailX++;
break;
case 'W': nowTailY--;
break;
case 'N': nowTailX--;
break;
default:
break;
}
if(map[nowTailX][nowTailY] == 1) {
return true;
} else if(map[nowTailX][nowTailY] == 0) {
return false;
}
return false;
}
// 명령에 따라 방향 바꾸기
static char changeDir(char now, char order) {
char postHead = ' ';
switch(now) {
case 'E':
if(order == 'L') {
postHead = 'N';
} else if(order == 'D') {
postHead = 'S';
}
break;
case 'S':
if(order == 'L') {
postHead = 'E';
} else if(order == 'D') {
postHead = 'W';
}
break;
case 'W':
if(order == 'L') {
postHead = 'S';
} else if(order == 'D') {
postHead = 'N';
}
break;
case 'N':
if(order == 'L') {
postHead = 'W';
} else if(order == 'D') {
postHead = 'E';
}
break;
default:
break;
}
return postHead;
}
}정리
- 처음 풀이를 했을 때 입력 받는 조건에 대해 이해를 잘 못 해서 틀렸었다.
- 적절한 자료구조를 이용하면 풀이가 더 쉬워진다.
