풀이방법
사용된 것:
큐
2022.03.02
큐를 활용했다.
이번 턴에 뱀 머리가 새롭게 이동해야 하는 칸의 좌표가 (row, col)이라 하자.
- 만약 (row, col)의 위치에 뱀의 몸이 있거나 벽이 있다면 게임을 종료하고, 현재 시간을 화면에 출력한다.
- 만약 (row, col)의 위치에 아무것도 없다면, 큐에 (row, col)을 넣어주고 큐의 반대쪽 끝에서 요소 하나를 poll 한다.
- 만약 (row, col)의 위치에 사과가 있다면, 큐에 (row, col)을 넣어주고 큐에서 아무것도 poll 하지 않는다.
방의 각 좌표에 무엇이 있는지는 2차원 정수 배열로 기록하였다.
해당 칸에 아무것도 없다면 0을, 뱀의 몸이나 머리가 있다면 1을, 사과가 있다면 2를 저장하였다.
코드
Java(2022.03.02)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static Queue<Point> queue; //게임 진행 시 사용할 큐
static int n, k, l; //방 크기, 사과 개수, 방향전환 횟수
static int[][] maze; //2차원 공간 배열(빈칸은 0, 뱀 몸은 1, 사과는 2)
static Point head; //뱀머리의 현재 위치
static int sec; //현재까지 게임이 진행된 시간(초)
//아래 두 배열은 방향전환 정보를 저장
static int[] time; //방향전환 타이밍
static boolean[] direction; //전환하는 방향(왼쪽은 true, 오른쪽은 false)
static int idx; //위 두 배열을 탐색할 때 쓸 인덱스 변수
static int to; //현재 뱀머리가 향하는 방향(0시, 3시, 5시, 9시 방향으로 표시)
static StringTokenizer st;
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
queue = new LinkedList<>();
//미로 크기 읽어오기
n = Integer.parseInt(br.readLine());
//2차원 미로 배열 선언.
maze = new int[n+1][n+1]; //편의를 위해 (n+1)*(n+1)크기로 선언
//사과 개수 읽어오기
k = Integer.parseInt(br.readLine());
//사과 위치를 읽어와서 미로 배열에 표시
for(int i = 0; i<k; i++) {
st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
maze[row][col] = 2;
}
//방향전환 횟수 읽어오기
l = Integer.parseInt(br.readLine());
time = new int[l];
direction = new boolean[l];
//방향전환 정보를 읽어와서 저장해두기
for(int i = 0; i<l; i++) {
st = new StringTokenizer(br.readLine());
time[i] = Integer.parseInt(st.nextToken());
if(st.nextToken().equals("L")) direction[i] = true;
else direction[i] = false;
}
//게임 진행하기
sec = 0;
idx = 0;
head = new Point(1,1); //뱀머리의 초기위치는 (1,1)
queue.add(new Point(1,1));
maze[1][1] = 1;
to = 3; //뱀머리의 초기 방향은 3시 방향
while(true) {
sec++;
//지금 방향을 바꾸어야 하는 경우
if(idx<l) {
if(sec == time[idx]+1) {
if(direction[idx]) {
//왼쪽으로 돌기
to = (to+9)%12;
}else {
//오른쪽으로 돌기
to = (to+3)%12;
}
idx++;
}
}
//현재 방향에 맞게 뱀 머리 이동
if(to == 0)head.row--;
if(to == 3)head.col++;
if(to == 6)head.row++;
if(to == 9)head.col--;
//이번에 머리가 이동한 칸의 내용물을 살피기
if(head.row>n || head.col>n || head.row == 0 || head.col == 0) {
//이번 칸이 방의 벽인 경우
break; //게임 종료
}
if(maze[head.row][head.col] == 1) {
//이번 칸에 뱀의 몸이 있을 경우
break; //게임 종료
}
if(maze[head.row][head.col] == 0) {
//이번 칸이 빈칸인 경우
queue.add(new Point(head.row,head.col)); //머리 위치를 큐에 넣기
Point tail = queue.poll(); //꼬리 위치를 큐에서 빼기
maze[tail.row][tail.col] = 0; //꼬리가 있던 칸을 0(빈칸)으로 업데이트
maze[head.row][head.col] = 1; //머리가 새로 들어간 칸을 1(뱀이 있음)로 업데이트
}
if(maze[head.row][head.col] == 2) {
//이번 칸에 사과가 있는 경우
queue.add(new Point(head.row,head.col)); //머리 위치를 큐에 넣기
maze[head.row][head.col] = 1; //머리가 새로 들어간 칸을 1(뱀이 있음)로 업데이트
}
}
System.out.print(sec);
}
}
class Point {
int row;
int col;
public Point(int row, int col) {
this.row = row;
this.col = col;
}
}Java(2022.03.02, 0초부터 각 초마다 게임 진행 상황을 콘솔창에서 확인할 수 있는 코드)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static Queue<Point> queue; //게임 진행 시 사용할 큐
static int n, k, l; //방 크기, 사과 개수, 방향전환 횟수
static int[][] maze; //2차원 공간 배열(빈칸은 0, 뱀 몸은 1, 사과는 2)
static Point head; //뱀머리의 현재 위치
static int sec; //현재까지 게임이 진행된 시간(초)
//아래 두 배열은 방향전환 정보를 저장
static int[] time; //방향전환 타이밍
static boolean[] direction; //전환하는 방향(왼쪽은 true, 오른쪽은 false)
static int idx; //위 두 배열을 탐색할 때 쓸 인덱스 변수
static int to; //현재 뱀머리가 향하는 방향(0시, 3시, 5시, 9시 방향으로 표시)
static StringTokenizer st;
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
queue = new LinkedList<>();
//미로 크기 읽어오기
n = Integer.parseInt(br.readLine());
//2차원 미로 배열 선언.
maze = new int[n+1][n+1]; //편의를 위해 (n+1)*(n+1)크기로 선언
//사과 개수 읽어오기
k = Integer.parseInt(br.readLine());
//사과 위치를 읽어와서 미로 배열에 표시
for(int i = 0; i<k; i++) {
st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
maze[row][col] = 2;
}
//방향전환 횟수 읽어오기
l = Integer.parseInt(br.readLine());
time = new int[l];
direction = new boolean[l];
//방향전환 정보를 읽어와서 저장해두기
for(int i = 0; i<l; i++) {
st = new StringTokenizer(br.readLine());
time[i] = Integer.parseInt(st.nextToken());
if(st.nextToken().equals("L")) direction[i] = true;
else direction[i] = false;
}
//게임 진행하기
sec = 0;
idx = 0;
head = new Point(1,1); //뱀머리의 초기위치는 (1,1)
queue.add(new Point(1,1));
maze[1][1] = 1;
to = 3; //뱀머리의 초기 방향은 3시 방향
while(true) {
//확인용 반복문
for(int i = 1; i<n+1; i++) {
for(int j = 1; j<n+1; j++) {
System.out.print(maze[i][j] + " ");
}
System.out.println();
}
System.out.println();
sec++;
//지금 방향을 바꾸어야 하는 경우
if(idx<l) {
if(sec == time[idx]+1) {
if(direction[idx]) {
//왼쪽으로 돌기
System.out.println("왼쪽으로 돌기");
System.out.println();
to = (to+9)%12;
}else {
//오른쪽으로 돌기
System.out.println("오른쪽으로 돌기");
System.out.println();
to = (to+3)%12;
}
idx++;
}
}
//현재 방향에 맞게 뱀 머리 이동
if(to == 0)head.row--;
if(to == 3)head.col++;
if(to == 6)head.row++;
if(to == 9)head.col--;
//이번에 머리가 이동한 칸의 내용물을 살피기
if(head.row>n || head.col>n || head.row == 0 || head.col == 0) {
//이번 칸이 방의 벽인 경우
System.out.println("벽에 부딪힘!");
break; //게임 종료
}
if(maze[head.row][head.col] == 1) {
//이번 칸에 뱀의 몸이 있을 경우
System.out.println("몸에 부딪힘!");
break; //게임 종료
}
if(maze[head.row][head.col] == 0) {
//이번 칸이 빈칸인 경우
queue.add(new Point(head.row,head.col)); //머리 위치를 큐에 넣기
Point tail = queue.poll(); //꼬리 위치를 큐에서 빼기
maze[tail.row][tail.col] = 0; //꼬리가 있던 칸을 0(빈칸)으로 업데이트
maze[head.row][head.col] = 1; //머리가 새로 들어간 칸을 1(뱀이 있음)로 업데이트
}
if(maze[head.row][head.col] == 2) {
//이번 칸에 사과가 있는 경우
queue.add(new Point(head.row,head.col)); //머리 위치를 큐에 넣기
maze[head.row][head.col] = 1; //머리가 새로 들어간 칸을 1(뱀이 있음)로 업데이트
}
}
System.out.print(sec);
}
}
class Point {
int row;
int col;
public Point(int row, int col) {
this.row = row;
this.col = col;
}
}'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| #2003 : 수들의 합 2 (0) | 2022.03.05 |
|---|---|
| #1431 : 시리얼 번호 (0) | 2022.03.05 |
| #2607 : 비슷한 단어 (0) | 2022.03.02 |
| #9012 : 괄호 (0) | 2022.03.02 |
| #2231 : 분해합 (0) | 2022.03.02 |