728x90
뱀
해설
처음에 이 문제를 풀 때, 제 시간에 풀지 못했다. 꼬리, 몸통, 머리 부분이 이해가 잘 안갔었는데 이 부분에 대한 해설은 다음과 같다.
# 꼬리, 몸통, 머리
예를들어 뱀이 (0, 0)에서 시작해서 계속 사과를 먹으며 우측으로 이동해 (0, 3)까지 간 상태라면
queue = (앞=꼬리) { (0,0), (0,1), (0,2), (0,3) } (뒤=머리) 가 된다.
사과를 못 먹어서 꼬리부분을 당겨야 되는 상황이라면 꼬리 위치의 값을 빈 값으로 설정하면 된다.
이 문제의 핵심은 Queue
를 사용한다는 것을 빨리 눈치 채야하는 것 같다. 그리고 나머지는 구현 문제 답게, 문제에 나와있는 조건들에 따라 차근차근 구현하면 되는 것 같다.
- Strategy
- 전략(Strategy) 이라는 클래스를 만들어
방향 정보
와초
를 필드로 가지게 했다.
- 전략(Strategy) 이라는 클래스를 만들어
- Position
- Position 은 뱀위 위치(꼬리, 몸통, 머리)를 나타내는 좌표를 담을 수 있도록 하였다.
알고리즘 문제들 중 방향(Ex. 회전 후 이동)
과 같은 문제 유형은 다음과 같은 코드가 거의 들어가는 것 같다.
// 방향 전환 D(right) 기준으로 동(초기방향) -> 남 -> 서 -> 북
// 방향 전환 L(left) 기준으로 동(초기방향) -> 북 -> 서 -> 남
private static int dx[] = {0, 1, 0, -1};
private static int dy[] = {1, 0, -1, 0};
초기 위치가 (1,1) 이며, 동쪽을 바라보고 있을 때, 오른쪽 방향(or 시계 방향)
으로 90 도로 회전하면 남쪽을 바라보게 된다. 그리고 남쪽으로 이동하면 (1,1) -> (2,1) 이 된다. 남쪽에서 다시 시계 방향으로 회전하면 서쪽을 바라보게 되고, 서쪽으로 이동하면 (2,1) -> (2,0) 이 된다.
이런식으로 방향에 따라 변화는 좌표를 계산하기 위한 함수
를 제공할 수 있는데 다음과 같다.
// 회전
public static int turn(int direction, char c) {
if (c == 'L') {
direction = (direction == 0) ? 3 : direction - 1;
} else {
direction = (direction + 1) % 4;
}
return direction;
}
문제에서 주어지는 방향 조건에 맞게 함수 내부 구현을 다르게 해주면 된다.
구현
class Strategy {
private int seconds;
private char direction;
public Strategy(int seconds, char direction) {
this.seconds = seconds;
this.direction = direction;
}
public int getSeconds() {
return seconds;
}
public char getDirection() {
return direction;
}
}
class Position {
private int x;
private int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
public class Main {
private static int N; // 보드의 크기
private static int K; // 사과의 위치
private static int L; // 방향 변환 횟수
private static int[][] square;
private static final int EMPTY = 0; // 빈 값
private static final int APPLE = Integer.MAX_VALUE; // 사과과 존재하는 위치
private static final int SNAKE = Integer.MIN_VALUE; // 뱀이 존재하는 위치
private static List<Strategy> strategies = new ArrayList<>(); // 이동 전략
// 방향 전환 D(right) 기준으로 동(초기방향) -> 남 -> 서 -> 북
// 방향 전환 L(left) 기준으로 동(초기방향) -> 북 -> 서 -> 남
private static int dx[] = {0, 1, 0, -1};
private static int dy[] = {1, 0, -1, 0};
public static void main(String[] args) {
input();
System.out.println(playDummyGame());
}
private static void input() {
Scanner sc = new Scanner(System.in);
// 게임판 생성
N = sc.nextInt();
square = new int[N + 1][N + 1]; // 외곽을 표시하기 위해서 N + 1 사이즈로 정사각형 보드 생성
// 사과 위치 저장
K = sc.nextInt();
for (int i = 0; i < K; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
square[x][y] = APPLE;
}
// 이동 전략 저장
L = sc.nextInt();
for (int i = 0; i < L; i++) {
strategies.add(new Strategy(sc.nextInt(), sc.next().charAt(0)));
}
}
private static int playDummyGame() {
// 초기 뱀 위치 1,1 (0,0 은 외곽임)
int x = 1;
int y = 1;
square[1][1] = SNAKE; // 현재는 뱀의 머리만 있음
int direction = 0; // 처음 바라보는 방향은 동쪽
int seconds = 0; // 경과 시간(초)
int index = 0; // 다음에 회전할 정보
Queue<Position> Q = new LinkedList<>();
Q.offer(new Position(x, y));
while(true) {
int nx = x + dx[direction];
int ny = y + dy[direction];
// 사각형 보드안에 존재하며, 뱀이 존재하는 위치가 아닐 경우
if(isInSquare(nx, ny) && square[nx][ny] != SNAKE) {
// 사과가 없으면 이동 후에 꼬리 제거
if (square[nx][ny] != APPLE) {
square[nx][ny] = SNAKE;
Q.offer(new Position(nx, ny));
// 꼬리 제거 코드
Position prev = Q.poll();
square[prev.getX()][prev.getY()] = EMPTY;
}
// 사과가 있다면 이동 후에 꼬리 그대로 두기
if (square[nx][ny] == APPLE) {
square[nx][ny] = SNAKE;
Q.offer(new Position(nx, ny));
}
} else { // 벽이나 뱀의 몸통과 부딪힌 경우
seconds++;
break;
}
// 다음 위치로 머리를 이동
x = nx;
y = ny;
seconds++;
if (index < L && seconds == strategies.get(index).getSeconds()) { // 회전할 시간인 경우 회전
direction = turn(direction, strategies.get(index).getDirection());
index += 1;
}
}
return seconds;
}
// 사각형 보드안에 존재하는 경우
private static boolean isInSquare(int x, int y) {
return 1 <= x && x <= N && 1 <= y && y <= N;
}
// 회전
public static int turn(int direction, char c) {
if (c == 'L') {
direction = (direction == 0) ? 3 : direction - 1;
} else {
direction = (direction + 1) % 4;
}
return direction;
}
}
728x90
'Algorithms > 문제 풀이' 카테고리의 다른 글
[BOJ 16234] 인구 이동 (0) | 2021.12.31 |
---|---|
[BOJ 1715] 카드 정렬하기 (0) | 2021.12.18 |
[BOJ 18352] 특정 거리의 도시 찾기 (0) | 2021.12.18 |
이것이 코딩 테스트다 : 모험가 길드 (0) | 2021.12.18 |
[BOJ 18406] 럭키 스트레이트 (0) | 2021.12.16 |