BOJ 3190) 뱀
- [ 기타 ]/백준, 프로그래머스
- 2022. 7. 1.
뱀 성공다국어
| 1 초 | 128 MB | 49416 | 20232 | 13459 | 39.229% |
문제
'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가 증가하는 순으로 주어진다.
출력
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
풀이
결론부터 말하자면,,, 푸는데 생각보다 애 많이먹었다. 코테대비를 위해 대충 tab키 누르면서 코딩하는 버릇 슬슬 줄이려고 노력하던 차에 내 기준에 애먹은 문제였음. 심지어 구글링해서 나오는 다른사람들 방법(dx dy쓰던데 유형화된 문제인가보다. 아니면 내가 바보거나)들이랑도 전혀 달라서 참고도 못함.
먼저 이 문제가 어렵게 느껴졌던 이유를 여러개 생각해봤다.
1. 문제의 조건이 많음: 간단한 문제처럼 보였지만 사실 신경써서 보지 않으면 헷갈릴만한 부분이 조금 있다.
- '먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다': 이 말은 머리를 확장시키고 꼬리를 줄이는 방식으로 구현해야 하며, 그 사이에 머리와 꼬리가 겹치지 않는지 검사하는 로직이 필요함을 의미한다. 뱀을 온전히 이동시킨 이후에 종료조건을 검사한다면 문제가 발생할 수 있다.
- 'X초가 끝난 뒤에 방향을 회전', '뱀은 매 초마다 이동': 뱀이 (0,0)에 위치한 채로 시작하면 시작하고 뱀이 움직이고 회전하는건가? 아니면 회전한 후에 움직이는것인가?... 나는 시작을 0초라고 두고 1초가 지나서 1초가 된 시점에 뱀이 현재 바라보는 방향으로 이동하고, 그 직후에 필요하다면 방향을 회전하는 것이라고 생각했다.
2. 자료구조의 다양성, 복잡함: 뱀이 움직이는 공간의 상태와 사과의 위치를 표현하기 위해서 2차원 boolean 배열, 뱀의 위치를 저장하기 위해서 큐, 시점과 방향 전환 정보를 저장하는데 해시맵, 상하좌우 정보를 표현하는데 int(enum도 가능), 위치 정보를 큐에 넣고 사용하기 위해서 별도의 inner class까지.. 추가로 배열을 N*N크기로 설정했다면 인덱스도 x,y모두 -1을 해주어야 한다. 단순히 숫자가 많기도 하지만 어떤 자료구조를 사용해야 깔끔하게 표현이 가능할지 고민하는것이 쉽지 않았다. (결국은 깔끔하지 않은 코드가 만들어졌다)
3. 꼬이는 머리: 이건 나의 문제이긴 한데 자료구조와 함께 변수들도 늘어나면서 어디에 어떤 조건을 추가해야 할지, 이 조건은 어디서 어떻게 검사해야 할지와 같은 생각들이 정리가 안된것 같다. 거의 4시간에 가까운 시간동안 크게 3번의 오류가 있었는데, 처음에는 종료조건을 벽에 부딪히는 케이스만 처리하고 몸에 부딪히는 케이스를 빠뜨렸고, 두번째로 위에서 이야기했던 머리와 꼬리가 순간적으로 겹치는 케이스가 빠졌고, 마지막으로는 코드를 수정하던 와중 x-1을 x=1로 잘못 쓰는 와중에 전체 코드를 되짚으며 주석을 추가하고 tc를 뒤져보며 시간을 낭비하는 그런 문제가 생겼던 것 같다.
코드 개선
1. 공간복잡도를 위해서 boolean[][]을 사용했는데, N을 보면 최대 100으로 배열의 크기는 최대 10000임을 알 수 있음. int형으로 해도 40000byte=40KB로 문제의 공간복잡도 제한에 한참 못미침. 대충 그냥 int형으로 하고 뱀이 있는상태를 2와 같이 추가해서 풀수도 있었다.
2. 반복되는 코드 줄이기. direction을 동서남북=1234로 설정하면서 진행방향별로 반복되는 코드가 있음. 구글링 해보니
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
이런식으로 만든다음에
int direction=0;
...
int nx = head.x+dx[direction];
int ny = head.y+dy[direction];
...
if(turn<L && tDirs.get(turn).x==time) {
direction = (direction+tDirs.get(turn).y)%4;
direction = direction==-1?3:direction;
turn++;
}
이렇게 활용하더라. dx와 dy를 direction이라는 인덱스를 이용해서 자연스럽게 컨트롤 할 수 있도록 하는 것 같다.
코드 전문
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;
public class Main {
static int time;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); //보드의 크기
int K = Integer.parseInt(br.readLine()); //사과의 개수
boolean[][] arr = new boolean[N][N]; //[0][0]~[N-1][N-1], 사과가 존재하면 true
Queue<Location> queue = new LinkedList<>();
Map<Integer, Character> map = new HashMap<>();
int direction; //1:상 2:하 3:좌 4:우
for(int i=0; i<K; i++) {
String input = br.readLine();
String[] str = input.split(" ");
int x = Integer.parseInt(str[0])-1;
int y = Integer.parseInt(str[1])-1;
arr[x][y] = true;
}
int L = Integer.parseInt(br.readLine());
for(int i=0; i<L; i++) {
String input = br.readLine();
String[] str = input.split(" ");
int X = Integer.parseInt(str[0]); //시간 경과
char C = str[1].charAt(0); //회전 방향
map.put(X, C);
}
Location loc = new Location(0,0);
int x = loc.x; //head x
int y = loc.y; //head y
direction=4;
time=0;
queue.add(loc);
while(true) {
// System.out.println();
// System.out.println("HEAD-x:"+x+",y:"+y);
// for (Location location : queue) {
// System.out.println("뱀:"+location.x+","+location.y);
// }
//뱀 이동
if(direction==1) { //위로 이동 (x-1, y)
Location newLoc = new Location(x-1, y);
queue.add(newLoc);
if(x>0 && !arr[x-1][y]) { //사과가 없을경우 꼬리에서 제거
Location tail = queue.remove();
if(tail.x==x-1 && tail.y==y) { //꼬리에 닿는경우
System.out.println(++time);
return;
}
}
else if(x>0 && arr[x-1][y]) //사과가 있을경우 사과 사라짐
arr[x-1][y] = false;
x = x-1;
}
else if(direction==2) { //아래로 이동 (x+1, y)
Location newLoc = new Location(x+1, y);
queue.add(newLoc);
if(x<N-1 && !arr[x+1][y]) { //사과가 없을경우 꼬리에서 제거
Location tail = queue.remove();
if(tail.x==x+1 && tail.y==y) { //꼬리에 닿는경우
System.out.println(++time);
return;
}
}
else if(x<N-1 && arr[x+1][y]) //사과가 있을경우 사과 사라짐
arr[x+1][y] = false;
x = x+1;
}
else if(direction==3) { //좌로 이동 (x, y-1)
Location newLoc = new Location(x, y-1);
queue.add(newLoc);
if(y>0 && !arr[x][y-1]) { //사과가 없을경우 꼬리에서 제거
Location tail = queue.remove();
if(tail.x==x && tail.y==y-1) { //꼬리에 닿는경우
System.out.println(++time);
return;
}
}
else if(y>0 && arr[x][y-1]) //사과가 있을경우 사과 사라짐
arr[x][y-1] = false;
y = y-1;
}
else if(direction==4) { //우로 이동 (x, y+1)
Location newLoc = new Location(x, y+1);
queue.add(newLoc);
if(y<N-1 && !arr[x][y+1]) { //사과가 없을경우 꼬리에서 제거
Location tail = queue.remove();
if(tail.x==x && tail.y==y+1) { //꼬리에 닿는경우
System.out.println(++time);
return;
}
}
else if(y<N-1 && arr[x][y+1]) //사과가 있을경우 사과 사라짐
arr[x][y+1] = false;
y = y+1;
}
//충돌 검사
if(x<0 || x>=N || y<0 || y>=N) { //머리가 벽에 닿는경우
System.out.println(++time);
// System.out.println("hey "+x+" "+y);
return;
}
else { //꼬리 말고 다른 몸일부에 닿는 경우
int cnt=0;
for(Location tmp : queue) {
if(tmp.x==x && tmp.y==y)
cnt++;
}
if(cnt>=2) {
// System.out.println("cnt:"+cnt);
System.out.println(++time);
return;
}
}
//회전 검사
time++;
if(map.containsKey(time) && map.get(time)=='L') {
if(direction==1) direction=3;
else if(direction==2) direction=4;
else if(direction==3) direction=2;
else if(direction==4) direction=1;
}
else if(map.containsKey(time) && map.get(time)=='D') {
if(direction==1) direction=4;
else if(direction==2) direction=3;
else if(direction==3) direction=1;
else if(direction==4) direction=2;
}
}
}
static class Location {
int x; int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
}
// 어떤 자료구조를 사용할지 (arr[][], map, queue...)
// 뱀이 바라보고 있는 방향
// 뱀을 구성하는 좌표들의 모임 (종료조건 검사)
// 'X초가 끝난 뒤에': 0초가 끝난 뒤에 = 1초의 시작? or 1초가 지난 후에?
// 꼬리를 먹는경우 문제가 발생 (add, remove 해버리고 검사를 하는경우)
// 'X초가 끝난 뒤에' 방향을 회전. 그렇다면 회전될것을 고려하여 유망성 검사?>>>X 아님..'[ 기타 ] > 백준, 프로그래머스' 카테고리의 다른 글
| BOJ 1103) 게임 (0) | 2022.08.13 |
|---|---|
| BOJ 1697) 숨바꼭질 (0) | 2022.07.29 |
| 프로그래머스) 가장 먼 노드 (0) | 2022.06.28 |
| BOJ 10026) 적록색약 (0) | 2022.06.26 |
| BOJ 2981) 검문 (0) | 2022.06.24 |