BOJ 17143
위 문제는 백준 사이트의 알고리즘 17143 문제에 관한 설명입니다.
문제
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다.
격자판의 각 칸은 (r, c)로 나타낼 수 있다.
r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
칸에는 상어가 최대 한 마리 들어있을 수 있다.
상어는 크기와 속도를 가지고 있다.
낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.
- 낚시왕이 오른쪽으로 한 칸 이동한다.
- 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
- 상어가 이동한다.
상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다.
상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다.
상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다.
왼쪽 위에 상어를 구분하기 위해 문자를 적었다.
상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다.
이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.
낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.
입력
첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)
둘째 줄부터 M개의 줄에 상어의 정보가 주어진다.
상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다.
(r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다.
d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.
출력
낚시왕이 잡은 상어 크기의 합을 출력한다.
package day1105;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main낚시왕 {
static int R;
static int C;
static int M;
static int answer;
static int[] dx = { 0, -1, 1, 0, 0 }; // 0 1 2 3 4
static int[] dy = { 0, 0, 0, 1, -1 };
static int[][] map;
static Shark[] list;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[R][C];
list = new Shark[M+1];
for (int i = 1; i <= M; i++) {
st= new StringTokenizer(br.readLine());
int sharkR = Integer.parseInt(st.nextToken())-1;
int sharkC = Integer.parseInt(st.nextToken())-1;
int sharkSpeed = Integer.parseInt(st.nextToken());
int sharkDir = Integer.parseInt(st.nextToken());
int sharkSize = Integer.parseInt(st.nextToken());
map[sharkR][sharkC] = i;// 각 상어들의 숫자, 맵에는 0이 빈칸이라 i가 1번부터 시작함.
list[i] = new Shark(sharkR, sharkC, sharkSpeed, sharkDir, sharkSize); // 리스트에 상어 정보들을 담아두자
}
for (int i = 0; i < C; i++) {// 낚시왕은 1칸씩 움직인다. 맨왼쪽부터 맨오른쪽까지 동작, 이후 종료
fishing(i);// 낚자
move();
}
System.out.println(answer);
}
public static void fishing(int index) {
for (int i = 0; i < R; i++) {// 하나씩 내려간다.
if (map[i][index] != 0) {// 상어발견
answer += list[map[i][index]].size;
list[map[i][index]] = null;
return;
}
}
}
public static void move() {
map = new int[R][C];
for (int i = 1; i <= M ; i++) {
if(list[i] == null) continue;
Shark temp = list[i];
int nextX = temp.x;
int nextY = temp.y;
int speed = temp.speed;
int direction = temp.dir;
if(direction == 1 || direction == 2) speed %= (R*2-2);
else if(direction == 3 || direction == 4) speed %= (C*2-2);
for (int j = 0; j < speed; j++) {
nextX += dx[direction];
nextY += dy[direction];
if (nextX < 0 || nextY < 0 || R <= nextX || C <= nextY) {// 경계밖으로 나감.
direction = changeDirection(direction);
nextX += dx[direction] *2 ;// 뒤돌아가
nextY += dy[direction] *2 ;
}
}
if (map[nextX][nextY] != 0) {
if (temp.size < list[map[nextX][nextY]].size) {
list[i] = null;
continue;
} else {
list[map[nextX][nextY]] = null;
}
}
map[nextX][nextY] = i;
list[i] = new Shark(nextX, nextY, temp.speed, direction, temp.size);
}
}
public static int changeDirection(int direction) {
if(direction == 1) {
direction = 2;
}
else if(direction == 2) {
direction = 1;
}
else if(direction == 3) {
direction = 4;
}
else if(direction == 4) {
direction = 3;
}
return direction;
}
public static boolean isIn(int nextX, int nextY) {
if (0 <= nextX && 0 <= nextY && nextX < R && nextY < C)
return true;
else
return false;
}
static class Shark {
int x;
int y;
int speed;
int dir;
int size;
Shark(int x, int y, int speed, int dir, int size) {
this.x = x;
this.y = y;
this.speed = speed;
this.dir = dir;
this.size = size;
}
}
}
이번 문제는 시뮬레이션 문제 였습니다.
static class Shark {
int x;
int y;
int speed;
int dir;
int size;
Shark(int x, int y, int speed, int dir, int size) {
this.x = x;
this.y = y;
this.speed = speed;
this.dir = dir;
this.size = size;
}
}
상어들에 대한 정보를 저장하기 위한 Shark 클래스입니다.
좌표와 속도, 방향, 크기가 저장됩니다.
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[R][C];
list = new Shark[M+1];
for (int i = 1; i <= M; i++) {
st= new StringTokenizer(br.readLine());
int sharkR = Integer.parseInt(st.nextToken())-1;
int sharkC = Integer.parseInt(st.nextToken())-1;
int sharkSpeed = Integer.parseInt(st.nextToken());
int sharkDir = Integer.parseInt(st.nextToken());
int sharkSize = Integer.parseInt(st.nextToken());
map[sharkR][sharkC] = i;// 각 상어들의 숫자, 맵에는 0이 빈칸이라 i가 1번부터 시작함.
list[i] = new Shark(sharkR, sharkC, sharkSpeed, sharkDir, sharkSize); // 리스트에 상어 정보들을 담아두자
}
입력부 입니다.
맵의 크기와 상어의 마릿수를 얻은 다음.
상어들을 하나씩 list에 저장합니다.
- 참고할 것은 list는 목록을 나타내기위해 배열의 변수명을 저렇게 한 것이지. list를 만든것은 아닙니다.
for (int i = 0; i < C; i++) {// 낚시왕은 1칸씩 움직인다. 맨왼쪽부터 맨오른쪽까지 동작, 이후 종료
fishing(i);// 낚자
move();
}
반복문 부분입니다.
이 부분은 fishing 함수를 이용해 현재 index에 있는 열의 상어를 한마리씩 낚아 올 것입니다.
move함수가 동작한다면 상어들은 자신에 대한 정보에 맞게 이동을 하고 맵에 저장될 것입니다.
public static void fishing(int index) {
for (int i = 0; i < R; i++) {// 하나씩 내려간다.
if (map[i][index] != 0) {// 상어발견
answer += list[map[i][index]].size;
list[map[i][index]] = null;
return;
}
}
}
fishing 함수입니다.
해당 index의 라인을 위에서부터 쭉 아래로 내려오다가
상어를 만나게 되면 상어를 잡은 크기만큼 answer에 저장합니다.
그리고 상어 목록의 해당 번째를 null 처리합니다.
public static void move() {
map = new int[R][C];
for (int i = 1; i <= M ; i++) {
if(list[i] == null) continue;
Shark temp = list[i];
int nextX = temp.x;
int nextY = temp.y;
int speed = temp.speed;
int direction = temp.dir;
if(direction == 1 || direction == 2) speed %= (R*2-2);
else if(direction == 3 || direction == 4) speed %= (C*2-2);
for (int j = 0; j < speed; j++) {
nextX += dx[direction];
nextY += dy[direction];
if (nextX < 0 || nextY < 0 || R <= nextX || C <= nextY) {// 경계밖으로 나감.
direction = changeDirection(direction);
nextX += dx[direction] *2 ;// 뒤돌아가
nextY += dy[direction] *2 ;
}
}
if (map[nextX][nextY] != 0) {
if (temp.size < list[map[nextX][nextY]].size) {
list[i] = null;
continue;
} else {
list[map[nextX][nextY]] = null;
}
}
map[nextX][nextY] = i;
list[i] = new Shark(nextX, nextY, temp.speed, direction, temp.size);
}
}
낚시왕을 잡았으니 이제 상어들을 움직일 차례입니다.
맵을 새로 만들어주는 방식으로 했습니다.
만약 상어 목록들을 보다가 상어가 null 이면 낚시왕에게 잡혔거나, 다른 상어에게 잡아먹힌 상태입니다.
따라서 그게 아닌경우에 아래쪽이 실행이 됩니다.
상어 한마리 마다 temp에 담아서 값들을 저장합니다.
이번 문제의 핵심은 speed를 bfs에 그대로 돌려서 작동하면 시간초과가 나오게 됩니다.
따라서 규칙성을 찾아서 speed의 값을 줄여야 했습니다.
그렇게 나온 규칙성은 map을 그리면 방향에 따라 R 또는 C * 2 - 2 가 되었을때
원래의 위치로 돌아오는 것을 확인했습니다.
따라서 %연산을 이용해 값을 축소시키고 bfs를 돌리게 됩니다.
만약 범위 밖을 나간다면 그것은 뒤를 돌아서 꺾어가야하기에 방향을 바꾼 후 한칸 뒤로 이동합니다.
다 움직이고 나서 그곳에 혹시나 다른 상어가 있다면 사이즈를 비교하고 잡아먹어 줍니다.
i번째 인덱스에다가 해당 상어에 대한 값을 다시 덮어씌웁니다.
public static int changeDirection(int direction) {
if(direction == 1) {
direction = 2;
}
else if(direction == 2) {
direction = 1;
}
else if(direction == 3) {
direction = 4;
}
else if(direction == 4) {
direction = 3;
}
return direction;
}
public static boolean isIn(int nextX, int nextY) {
if (0 <= nextX && 0 <= nextY && nextX < R && nextY < C)
return true;
else
return false;
}
changeDirection 함수와 isIn 함수는
범위를 벗어날 때 방향을 바꿔주는 함수와, 범위의 안인지 확인하는 함수입니다.