2019. 4. 10. 23:04ㆍ카테고리 없음
문제
https://www.acmicpc.net/problem/10875
10875번: 뱀
가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 (−L, −L), 그리고 맨 오른쪽 맨 위 칸의 좌표는 (L, L)이다. x좌표는 왼쪽에서 오른쪽으로 갈수록, y좌표는 아래에서 위로 갈수록 증가한다. 이 격자판의 (0, 0) 칸에 한 마리의 뱀이 자리를 잡고 있다. 처음에는 뱀의 크기가 격자
www.acmicpc.net
풀이
처음 풀이가 시간초과 가 나왔다.
아래 시간초과 코드 보기
package bj.test.ex02;
import java.util.ArrayList;
import java.util.Scanner;
public class Snake {
static int L, N;
static boolean out = false; // true 되면 게임 종료
static long result = 1; // 몇 초 뒤에 숨을 거두는지 알려주기
static class Rotate{
int t;
String dir;
Rotate(int t, String dir){
this.t = t;
this.dir = dir;
}
}
static class Coordi{
int x;
int y;
Coordi(int x, int y){
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
L = sc.nextInt();
N = sc.nextInt();
Rotate[] rot = new Rotate[N];
for(int i = 0; i < N; i++) {
int t = sc.nextInt();
String d = sc.nextLine().replaceAll(" ", "");
rot[i] = new Rotate(t, d);
}
// 뱀의 몸의 정보를 어떻게 저장하징 ? 흠
// for(int i = 0; i < N; i++) {
// System.out.println(rot[i].t + " " + rot[i].dir);
// }
// 몸이 계속 늘어남
// out
// 뱀의 머리가 격자판 밖으로 나가거
// 머리가 자신의 몸을 부딪히면
arr.add(new Coordi(0, 0));
solution(rot, rot[0].t, 0, 1);
//"R"
// 현재 방향과 새로운 방향을 기억해야한다.
// 횟수를 출력해야한다. 음 음 음음음음음
// 배열을 계속 돌려보다가 out = true가 되면 회전을 중지하고 result를 출력한다.
System.out.println(result);
sc.close();
}
// 회전 메소드
// 이동 후
// out의 경우를 확인한다.
//[4][2]
static int[][] dd = {{-1,0}, {0, 1}, {1,0}, {0, -1}};
static ArrayList<Coordi> arr = new ArrayList<Coordi>(); // 뱀의 몸통 정보
private static void solution(Rotate[] rot, int leftT, int idx, int dir) {
// 방향
// 이전 방향과 비교해야한다.
// 현재 시작 인덱스 몇번째 늘림인지
// 회전 여부 확인 엥 엥 !?????
// t를 넘겨서 t-1 반복 결국 그 값이 0 이면 회전하게 하자
if(out) {
result -= 1;
return;
}
if(leftT == 0) {// 회전
//방향 회전 진행
// 0 왼쪽 1 위쪽 2 오른쪽 3 아래쪽
if(rot[idx].dir == "L") {
dir -= 1;
if(dir < 0 ) dir = 3;
}else {
dir += 1;
if(dir > 3) dir = 0;
}
idx++;
if(idx == rot.length) { // 예외처리 (게임끝)
idx = 0;
}
leftT = rot[idx].t;
}
// 회전하고 눈앞에 몸통이 있는지 확인할까 아니면
// 이동했을 때 몸통과 같은 위치면 확인할까 꾸엥
// 몸통 늘리기
int tx, ty;
tx = arr.get(arr.size()-1).x; // 현재 뱀의 머리 위치
ty = arr.get(arr.size()-1).y;
tx += dd[dir][0];
ty += dd[dir][1];
// 장외
if(Math.abs(tx) > L || Math.abs(ty) > L) {
out = true;
}
// 몸통 부딪히기
for(int i = 0; i < arr.size(); i++) {
if(arr.get(i).x == tx && arr.get(i).y == ty) out = true;
}
result++;
arr.add(new Coordi(tx, ty));
solution(rot, leftT-1, idx, dir);
}
}
이유 1 ) 뱀의 몸통 정보를 ArrayList<Coordi> 로 담아서 새롭게 이동한 x, y 좌표가 겹치면 몸통이 부딪혔다고 가정함. -> 투머치 시간 ?
이유 2 ) 회전 정보를 가져오는 인덱스가 끝없이 올라감 (IndexOutOfRangeException)
이유 3 ) 주어진 N개 갯수만큼 몸통 늘리기 및 회전을 다했을 경우 게임이 종료되는 줄 알았음.
장외로 떨어지거나 몸통이 부딪히지 않는 이상 주어진 이동(회전)정보를 가지고 몸통을 늘려야 함.
그 외 고려할 점 4 ) 다음과 같은 케이스에서 StackOverflowError 발생 ... (참고 블로그에서 제공)
100000000
5
100000000 L
100000000 L
200000000 L
199999999 L
199999999 L
=> 899999997
참고 블로그에서 말하는 *문제 풀 때 주의할 점* 을 나는 고려하지 못한 것이다 !!!
? L 보다는 N 을 사용해서 어떻게 풀어야 할까 ?
1. 뱀의 몸통 정보를 좌표로 기록하지 말고 선분으로 기록하자.
2. 현재 방향과 위치에서 최대로 이동할 수 있는 시간을 구한다. (엄청 큰 값의 테스트에서 효율 높이기)
→ 입력받은 뱀 이동 시간이 최대 이동 시간보다 크면 충돌
→ 충돌하지 않는다면 새로운 이동(뱀 몸통) 선분을 추가한다.
3. 경계(장외로 빠져나가는 경우) 선분도 뱀 몸통에 넣어둔다.
참고 블로그에서 선분을 저장하는 Line 클래스부터 이해가 안된다............... 내 식대로 선분을 저장하자... 눈물....
와 최대로 이동할 수 있는 시간을 구하는게 처음에 이해가 안되서 오래 헤맸다.
뱀의 이동 방향과 이동 방향에 있는 가장 가까운 선분과의 거리를 구하면 되는데
가장 가까운 선분과 부딪혔을 때의 상황이 이해가 안되었다.
가장 가까운 선분과 부딪혔을 때의 경우는 다음과 같다.
이동 방향이 위쪽(UP)일 경우 부딪칠 수 있는 가장 가까운 선분이 수평, 수직인 경우로 2가지가 나뉘는데 그림과 같이 부딪힐 수 있다.
이동 방향이 오른쪽(RIGHT)일 경우 부딪칠 수 있는 선분이 마찬가지로 수평, 수직으로 나뉜다.
우리는 여기서 가장 가까운 선분과 부딪히지 않는 경우를 찾아내서 최대로 이동할 수 있는 시간을 구해낸다.
이 부분의 조건을 주의하자
코드
package bj.test.ex02;
import java.util.ArrayList;
import java.util.Scanner;
public class Snake {
static int L, N;
static boolean out = false; // true 되면 게임 종료
static long result = 0L; // 몇 초 뒤에 숨을 거두는지 알려주기
static int maxT, time;
static ArrayList<Line> LineArr = new ArrayList<Line>(); // 뱀의 몸통 정보
static final int INF = 1000000000; // 최대값
static final int LEFT = 0;
static final int UP = 1;
static final int RIGHT = 2;
static final int DOWN = 3;
// 0 왼쪽 1 위쪽 2 오른쪽 3 아래
static int[][] dd = {{-1,0}, {0, 1}, {1, 0}, {0,-1}};
static class Rotate{
int t;
String dir;
Rotate(int t, String dir){
this.t = t;
this.dir = dir;
}
}
static class Line{
int x1, y1, x2, y2;
int dir; // 수평인지 수직인지 알려준다.
Line(int x1, int y1, int x2, int y2){
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
if(x1 == x2) { // 수직
this.dir = 0;
}else { // 수평
this.dir = 1;
}
letSort();
}
private void letSort() {
int temp;
if(x1 > x2) {
temp = x2;
this.x2 = x1;
this.x1 = temp;
}
if(y1 > y2) {
temp = y2;
this.y2 = y1;
this.y1 = temp;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
L = sc.nextInt();
N = sc.nextInt();
Rotate[] rot = new Rotate[N];
int rotateDir = 1;
for(int i = 0; i < N; i++) {
int t = sc.nextInt();
String d = sc.nextLine().replaceAll(" ", "");
rot[i] = new Rotate(t, d);
}
// 경계선 - 아래, 왼, 위, 오른쪽 순서
LineArr.add(new Line(-L-1,-L-1, L+1, -L-1));
LineArr.add(new Line(-L-1,-L-1, -L-1, L+1));
LineArr.add(new Line(-L-1, L+1, L+1, L+1));
LineArr.add(new Line( L+1, L+1, L+1, -L-1));
// 시작
int x = 0, y = 0; // 뱀의 현재 머리위치
int dir = RIGHT;
// 회전 및 이동할 수 있는 최대 시간 구하기
for(int i = 0; i <= N; i++) {
if( i < N ) {
time = rot[i].t;
rotateDir = (rot[i].dir.equals("L") ? -1:1);
} else {
time = INF;
rotateDir = -1;
}
maxT = INF;
for(int j = 0; j < LineArr.size(); j++) {
Line compareLine = LineArr.get(j);
// Line.dir == 0 수직
// Line.dir == 1 수평
switch(dir) {
case LEFT :
if((compareLine.dir == 0 && x > compareLine.x1 && y >= compareLine.y1 && y <= compareLine.y2)
|| (compareLine.dir == 1 && y == compareLine.y1 && x > compareLine.x2 )) {
maxT = Math.min(maxT, x - compareLine.x2);
}
break;
case RIGHT :
if((compareLine.dir == 0 && x < compareLine.x1 && y >= compareLine.y1 && y <= compareLine.y2 )
|| (compareLine.dir == 1 && x < compareLine.x1 && y == compareLine.y1 )) {
maxT = Math.min(maxT, compareLine.x1 - x);
}
break;
case UP :
if((compareLine.dir == 0 && x == compareLine.x1 && y < compareLine.y1)
||(compareLine.dir == 1 && x >= compareLine.x1 && x <= compareLine.x2 && y < compareLine.y1)) {
maxT = Math.min(maxT, compareLine.y1 - y);
}
break;
case DOWN :
if((compareLine.dir == 0 && x == compareLine.x1 && y > compareLine.y2)
|| (compareLine.dir == 1 && x >= compareLine.x1 && x <= compareLine.x2 && y > compareLine.y1)) {
maxT = Math.min(maxT, y - compareLine.y2 );
}
break;
}
}
// 현재 위치와 방향에서 최대로 이동할 수 있는 시간이
// 입력받은 뱀 이동 시간보다 같거나 작으면 충돌
if(maxT <= time) { // 충돌
result += maxT;
System.out.println(result);
sc.close();
return;
}
// 충돌 X
result += time;
int nextX = x + dd[dir][0] * time;
int nextY = y + dd[dir][1] * time;
//현재 선분 추가
Line curLine = new Line(x,y,nextX,nextY);
LineArr.add(curLine);
// 다음진행설정
x = nextX;
y = nextY;
dir = (dir + rotateDir + 4) % 4;
}
sc.close();
}
}
흐름
- Line 클래스
( x1, y1, x2, y2 )값을 가지는 좌표 클래스 . 뱀의 몸통 정보를 선분으로 표현한다.
- Rotate 클래스
이동 시간 및 회전 방향을 가지는 클래스
참고
- 테스트 케이스도 추가로 제공해주시고 너무 친절한 블로그 ! 감삼다 !
https://stack07142.tistory.com/173
BOJ#10875 뱀
BOJ#10875 뱀 * 문제 https://www.acmicpc.net/problem/10875 * 풀이 ※ 문제 풀 때 주의할 점 주어진 입력의 크기를 잘 살펴봅시다. L <= 10^8이므로 L은 1억이고 맵 사이즈는? (2억+1) * (2억+1) 맵 사이즈가 작..
stack07142.tistory.com
- 이 방법도 넘모 좋은것 같다.
https://baactree.tistory.com/11
[BOJ] 백준 10875번: 뱀
뱀 문제 (0, 0) 에서 뱀이 오른쪽 방향을 보고 출발한다. n개의 명령 (이전 명령으로 부터 t시간 뒤에, dir 방향으로 머리를 돌림)을 수행하면서 격자판 밖으로 나가거나 자신의 몸에 부딪히는 시간을 구하는 문제..
baactree.tistory.com
주어진 변수의 범위를 꼭 확인 후 알고리즘을 짜자
이전 코딩테스트에서도 범위 문제로 히든케이스를 못 넘겨놓고 이 부분을 고려하지 않는 나는 바보멍총이 !