[BOJ 3190] 뱀 (Java, BFS, 구현)알고리즘/그래프 탐색2023. 6. 14. 17:27
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/3190
풀이
- 주어진 조건에 맞게 BFS, 시뮬레이터 구현 하는 문제
- Queue를 활용하여 뱀의 위치 정보를 관리하고, 맵 데이터를 갱신 시켜 줌
게임 조건
게임은 N * N 보드 위에서 진행되고, 게임이 시작할 때 뱀은 맨위 맨 좌측에 위치하고 뱀의 길이는 1이다.
뱀은 맨 처음 오른쪽으로 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 구한다
방향 전환*(실수 포인트)
- 방향 전환 정보는 class를 정의하고 LinkedList에 담아서 정해진 시간에 방향 전환하도록 함
이동할 때
- Queue 의 선입선출(FIFO) 성질을 활용하여 뱀의 위치 정보를 관리할 수 있도록 함
- int[][] GAME_MAP에 뱀(2)에 대한 정보 표시
Queue 에 뱀의 시작 위치 기록
( 1, 1 ) |
GAME_MAP (0 : 빈 필드, 1 : 사과, 2 : 뱀)
~< (2) |
0 또는 1 |
0 | 0 |
1) 사과(1)가 없는 경우
- 오른쪽으로 한칸 이동
- Queue에서 이전 위치 정보(1, 1)를 꺼내서 0으로 갱신
0 | ~< (2) |
0 | 0 |
- Queue에 이동한 뱀의 현재 위치 정보를 입력
( 1, 2 ) |
2) 사과(1)가 있는 경우
- 오른쪽으로 한칸 이동
- 사과(1)가 있기 때문에 뱀의 길이가 증가
~ (2) |
~< (2) |
0 | 0 |
- Queue에 이동한 뱀의 위치 정보를 입력
( 1, 1 ), ( 1, 2 ) |
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static int N, K, L, TIME; // N : 보드 크기, K : 사과의 개수 , L: 방향 변환 명령 횟수
static int[][] GAME_MAP;
static List<Cmd> CMD_LIST = new LinkedList<>();
static int[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 초기 오른쪽
static class Cmd {
int timing;
String direction;
public Cmd(int timing, String direction) {
this.timing = timing;
this.direction = direction;
}
}
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
GAME_MAP = new int[N + 1][N + 1];
st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
// 빈 공간 : 0, 사과 위치 : 1, 뱀 : 2
for(int i = 1; i <= K; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
GAME_MAP[x][y] = 1;
}
// 방향 전환 정보
st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
for(int i = 1; i <= L; i++) {
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
String c = st.nextToken();
CMD_LIST.add(new Cmd(t, c));
}
}
static void bfs(int startX, int startY) {
// 뱀의 정보를 가지고 있음
Queue<Integer> que = new LinkedList<>();
que.add(startX);
que.add(startY);
GAME_MAP[startX][startY] = 2;
int pointX = startX, pointY = startY;
int dirIdx = 0; // 0 ~ 3
Cmd cmd = CMD_LIST.remove(0);
while(!que.isEmpty()) {
TIME += 1;
pointX += DIRECTION[dirIdx][0];
pointY += DIRECTION[dirIdx][1];
// 벽에 부딪히는 경우
if(pointX < 1 || pointY < 1 || pointX > N || pointY > N) break;
// 자기 자신을 물었는가
if(GAME_MAP[pointX][pointY] == 2) break;
// 사과 없는 경우
if(GAME_MAP[pointX][pointY] == 0) {
int x = que.poll(), y = que.poll();
GAME_MAP[x][y] = 0;
}
// 뱀의 머리 이동
GAME_MAP[pointX][pointY] = 2;
que.add(pointX);
que.add(pointY);
if(TIME == cmd.timing) {
dirIdx = getDirectionIdx(dirIdx, cmd.direction);
if(!CMD_LIST.isEmpty()) {
cmd = CMD_LIST.remove(0);
}
}
}
System.out.println(TIME);
}
static int getDirectionIdx(int current, String cmd) {
int result;
if("D".equals(cmd)) {
result = (current + 1) % 4;
} else {
result = current - 1;
if(result < 0) result = 3;
}
return result;
}
static void pro() {
bfs(1, 1);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
반응형
'알고리즘 > 그래프 탐색' 카테고리의 다른 글
[BOJ2573] 빙산 (DFS, BFS, 그래프 탐색) (0) | 2023.09.21 |
---|---|
[BOJ 2636] 치즈 (Java, BFS) (0) | 2023.06.15 |
[BOJ 16234] 인구 이동 (Java, BFS, 구현) (0) | 2023.06.14 |
[BOJ 2638] 치즈 (Java, BFS) (0) | 2023.06.14 |
[BOJ 9466] 텀 프로젝트 (Java, DFS) (0) | 2023.06.14 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!