https://www.acmicpc.net/problem/23288
23288번: 주사위 굴리기 2
크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼
www.acmicpc.net
문제를 보자마자 BFS를 이용하는 문제라는 느낌이 왔다.
문제에 나와있는 주사위의 이동 과정은 순서대로 구현하고 점수를 구하는 부분에서 BFS를 사용했다.
처음에는 주사위의 아랫면을 저장하는 변수를 설정하고 현재 주사위의 아랫면과 방향에 따라 주사위의 아랫면을 바꾸는 함수를 만들어 다음 아랫면을 반환하도록 했다.
하지만 이 방식대로 하니 문제가 있었다. 특정 숫자의 동서남북이 주사위의 상태에 따라 다르다는 것을 생각하지 못하고 무조건 정해진 값을 반환하도록 했다.
그림으로 나타내면
위 사진에서 주사위는 서쪽으로 이동해 아랫면이 4로 바뀌었다. 그 후 북쪽으로 이동해 2로 바뀌었다.
위 사진에서는 북쪽으로 이동해 아랫면이 2도 바뀐 후 서쪽으로 이동해 아랫면이 4로 바뀐다.
그 후 북쪽으로 이동해 아랫면이 1로 바뀐다.
두 사진에서 마지막 이동에서 똑같이 아랫면이 4인 상태에서 북쪽으로 이동했지만 경우가 다르다.
나는 이 당연한 걸 머리로만 대충 생각하고 코드를 짜다가 놓치고 말았다....
그래서 주사위를 2차원 배열에 저장하고 이 배열의 상태를 바꾸는 함수를 다시 만들었다.
위 사진 처럼 주사위의 상태를 저장했다.
static int BFS(int x, int y, int val, int score) {
queue.poll();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M)
if (map[nx][ny] == val && visit[nx][ny] == false) { //같다
visit[nx][ny] = true; //방문 처리
queue.add(new Pair(x + dx[i], y + dy[i]));
}
}
if (!queue.isEmpty())
return BFS(queue.peek().x, queue.peek().y, val, score + 1);
return score;
}점수를 구하는 BFS 부분이다. 현재 위치에서 상, 하, 좌, 우를 보며 이전에 방문하지 않고 이동가능한 곳이라면 값이 같은지 확인한다. 값이 같다면 큐에 추가해준다.
큐가 비어있지 않은 동안 재귀 호출을 해준다.
x, y는 현재 확인하는 위치, val은 같아야 하는 값, score는 점수이다.
마지막으로 점수를 반환해준다.
static void move(int dir, int index) {
if (index == K) return;
int nx = x + dx[dir]; //다음 위치
int ny = y + dy[dir];
if (!(nx >= 0 && ny >= 0 && nx < N && ny < M)) { //이동 불가능
nx -= 2 * dx[dir]; //반대로 가도록
ny -= 2 * dy[dir];
dir = (dir + 2) % 4;
}
checkDice(dir); //주사위 이동
queue.add(new Pair(nx, ny)); //현재 아래 미리 추가
visit[nx][ny] = true; //방문 처리
result += map[nx][ny] * BFS(nx, ny, map[nx][ny], 1); //점수 획득
x = nx; //위치 이동
y = ny;
if (map[x][y] < dice[3][1]) //방향 바꾸기
dir = (dir + 1) % 4;
else if (map[x][y] > dice[3][1])
dir = (dir + 3) % 4;
initVisit(); //방문 처리 초기화
move(dir, index + 1);
}주사위를 이동하는 함수이다. index가 K와 같다면 종료한다.
nx, ny는 다음 이동 위치이다. 현재 방향에 맞게 이동한다.
만약 이동한 위치가 이동 불가능 하다면 반대로 가도록 해준다.
checkDice 함수를 통해 현재 방향에 맞게 주사위의 상태를 바꿔준다.
다음으로 BFS를 통해 점수를 구하고 result함수에 더해준다.
지도의 값과 주사위의 아랫면 값에 따라 방향을 바꿔주고 initVisit를 통해 BFS과정에서 방문 처리된 부분들을 다시 초기화 해준다.
그 후 재귀 호출
//동 0, 남 1, 서 2, 북 3
static void checkDice(int dir) { //주사위 이동
int temp;
switch (dir) {
case 0:
temp = dice[1][1];
dice[1][1] = dice[1][0];
dice[1][0] = dice[3][1];
dice[3][1] = dice[1][2];
dice[1][2] = temp;
break;
case 1:
temp = dice[0][1];
dice[0][1] = dice[3][1];
dice[3][1] = dice[2][1];
dice[2][1] = dice[1][1];
dice[1][1] = temp;
break;
case 2:
temp = dice[1][0];
dice[1][0] = dice[1][1];
dice[1][1] = dice[1][2];
dice[1][2] = dice[3][1];
dice[3][1] = temp;
break;
case 3:
temp = dice[0][1];
dice[0][1] = dice[1][1];
dice[1][1] = dice[2][1];
dice[2][1] = dice[3][1];
dice[3][1] = temp;
}
}주사위의 상태를 바꿔주는 함수이다.
전체 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N, M, K, result = 0;
static int x = 0, y = 0;
static int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
static int[][] map, dice = {{0, 2, 0}, {4, 1, 3}, {0, 5, 0}, {0, 6, 0}};
static Boolean[][] visit;
static Queue<Pair> queue = new LinkedList<>();
static class Pair {
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static int BFS(int x, int y, int val, int score) {
queue.poll();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M)
if (map[nx][ny] == val && visit[nx][ny] == false) { //같다
visit[nx][ny] = true; //방문 처리
queue.add(new Pair(x + dx[i], y + dy[i]));
}
}
if (!queue.isEmpty())
return BFS(queue.peek().x, queue.peek().y, val, score + 1);
return score;
}
//동 0, 남 1, 서 2, 북 3
static void move(int dir, int index) {
if (index == K) return;
int nx = x + dx[dir]; //다음 위치
int ny = y + dy[dir];
if (!(nx >= 0 && ny >= 0 && nx < N && ny < M)) { //이동 불가능
nx -= 2 * dx[dir]; //반대로 가도록
ny -= 2 * dy[dir];
dir = (dir + 2) % 4;
}
checkDice(dir); //주사위 이동
queue.add(new Pair(nx, ny)); //현재 아래 미리 추가
visit[nx][ny] = true; //방문 처리
result += map[nx][ny] * BFS(nx, ny, map[nx][ny], 1); //점수 획득
x = nx; //위치 이동
y = ny;
if (map[x][y] < dice[3][1]) //방향 바꾸기
dir = (dir + 1) % 4;
else if (map[x][y] > dice[3][1])
dir = (dir + 3) % 4;
initVisit(); //방문 처리 초기화
move(dir, index + 1);
}
private static void initVisit() {
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
visit[i][j] = false;
}
//동 0, 남 1, 서 2, 북 3
static void checkDice(int dir) { //주사위 이동
int temp;
switch (dir) {
case 0:
temp = dice[1][1];
dice[1][1] = dice[1][0];
dice[1][0] = dice[3][1];
dice[3][1] = dice[1][2];
dice[1][2] = temp;
break;
case 1:
temp = dice[0][1];
dice[0][1] = dice[3][1];
dice[3][1] = dice[2][1];
dice[2][1] = dice[1][1];
dice[1][1] = temp;
break;
case 2:
temp = dice[1][0];
dice[1][0] = dice[1][1];
dice[1][1] = dice[1][2];
dice[1][2] = dice[3][1];
dice[3][1] = temp;
break;
case 3:
temp = dice[0][1];
dice[0][1] = dice[1][1];
dice[1][1] = dice[2][1];
dice[2][1] = dice[3][1];
dice[3][1] = temp;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
K = sc.nextInt();
map = new int[N][];
visit = new Boolean[N][];
for (int i = 0; i < N; i++) {
map[i] = new int[M];
visit[i] = new Boolean[M];
for (int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
visit[i][j] = false;
}
}
move(0, 0);
System.out.println(result);
}
}'코테 > JAVA' 카테고리의 다른 글
| [백준 17837 / JAVA ] 새로운 게임 2 (0) | 2023.08.23 |
|---|---|
| [백준 14501 / JAVA] 퇴사 (0) | 2023.08.17 |
| [ALGOSPOT - SUSHI/JAVA] 회전초밥 (1) | 2023.07.31 |
| [백준 20055 / JAVA] 컨베이어 벨트 위의 로봇 (0) | 2023.07.24 |
| [백준 14502 / JAVA] 연구소 (0) | 2023.07.12 |