https://www.acmicpc.net/problem/17143
17143번: 낚시왕
낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.
www.acmicpc.net
코드설명
구현(Implementation) + 시뮬레이션(Simulation) 을 활용하는 문제입니다.
문제에서 유의해야할점들입니다.
0. 상어가 모두 이동한 후에 상어가 서로 잡아먹습니다.
이에 대한 처리를 위해 newMap[][] 과 같이 새로운 2차원 배열을 생성하여 상어를 이동시키며 바로바로 처리할 수 있고, 이전의 상어의 정보 또한 잃어버리지 않고 작업할 수 있습니다.
1. 처음에 Shark[][] map 값을 활용해서 만약 상어가 먹힌다면 null을 처리하였지만, 이전에 이미 연결된 주소값 또한 같이 초기화되어 모두 null값으로 초기화되지 않게해야합니다. 그렇게 하기 위해 새로 Shark가 이동한 newMap을 만들어주고 따로 진행했습니다. 이떄 유의해야할점은 얕은복사가 아닌 깊은복사를 활용하여 값을 복사시켜주어야합니다.
처음에 shark[][] map 배열 1개만 가지고서 처리할때 null처리하여 먹힌 것을 표현하였지만, 참조형이기에 값이 같이 변동되어 관리가 안됩니다.
//만약 이동한 칸에 상어가있따면 크기를 비교하여 서로 잡아먹도록합니다.
if(newMap[nr][nc] != null) {
Shark before = newMap[nr][nc]; //미리 도착한 상어.
if(before.size < temp.size ) { //만약 새로운게 더 크다면,
newMap[nr][nc] = new Shark(temp.r, temp.c, temp.moveable, temp.dir, temp.size);
// map[row][col] = null; //이렇게하면 연결된 것까지 사라진다.
}
}else if(newMap[nr][nc] == null) {
newMap[nr][nc] = new Shark(temp.r, temp.c, temp.moveable, temp.dir, temp.size);
// Map[row][col] = null;
}
아예 새로운 newMap을 생성하여 진행합니다.
newMap = new Shark[R][C];
2. 시간초과를 피하기 위해 아래의 식을 할용합니다. 문제에서 주어진 s 속력값의 크기는 1000 입니다. 이떄 모든 상어가 1000번씩 하나씩 이동할경우 시간초과가 납니다. 원래 위치로 돌아오는 경우는 무시하기 위해 아래의 식을 활용해서 진행합니다.
int rMoveableCnt = temp.moveable % ( 2 * (R - 1));
int cMoveableCnt = temp.moveable % ( 2 * (C - 1));
3. 처음에는 상어의 위치만 배열에 저장시켜두고 진행하였지만, 이렇게할경우 이후에 상어를 이동시킨 후 서로 먹히도록 처리할때, 혹은 낚시왕이 상어를 먹을때 모든 상어 저장배열을 다 돌아야합니다. 이 방법은 시간초과의 위험성이 존재하여 이후에 map, newMap을 활용하여 손쉽게 행과 열을 처리할 수 있게하고, 낚시왕이 상어낚시를 하기 편하게 로직을 처리할 수 있었습니다.
4. 상어가 이동할떄 만약 0 번쨰에서 이동한다면, -1번째가 아닌 1번째로 직접 처리해줍니다.
반대로, R-1번째에서 R번째로 이동한다면, R-2 번째로 이동시켜줍니다.
int rMoveableCnt = temp.moveable % ( 2 * (R - 1));
int cMoveableCnt = temp.moveable % ( 2 * (C - 1));
if(temp.dir == 0 || temp.dir == 1) {
for(int movecnt = 0; movecnt<rMoveableCnt;movecnt++) {
nr += dx[temp.dir];
if(nr < 0) {
temp.dir = changeDir(temp.dir);
nr = 1;
}
if(nr >= R) {
temp.dir = changeDir(temp.dir);
nr = R - 2;
}
}
}
if(temp.dir == 2 || temp.dir == 3) {
for(int movecnt = 0; movecnt<cMoveableCnt;movecnt++) {
nc += dy[temp.dir];
if(nc >= C) {
temp.dir = changeDir(temp.dir);
nc = C - 2;
}
if(nc < 0) {
nc = 1;
temp.dir = changeDir(temp.dir);
}
}
}
문제 접근시 중요했던 부분은
1. Shark[][] map, newMap을 선언하여 이동시킬때의 시점과 이동 시점을 분리시킨다.
2. 시간초과 해결을 위해 원상태로 되돌아오는 이동을 % 연산을 통해 최적화시킨다. 이떄 사소하게는 0 번째에는 1번쨰로, R-1번째에는 R-2번쨰로 이동시키는 것과 같은 처리를 해준다.
위의 사항들을 유의한다면 푸는데 도움이 될 것 같습니다.
코드
newMap, map을 활용하여 상어가 이동했을경우의 배열을 만들고 이동한 후 처리하도록 작업합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int R, C, M, N;
public static int[][] arr;
public static Shark[][] map;
public static Shark[][] newMap;
public static Person person;
public static int answer = 0;
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());
person = new Person(-1, 0);
map = new Shark[R][C];
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken()); //속력
int d = Integer.parseInt(st.nextToken()); //방향
int z = Integer.parseInt(st.nextToken()); //크기
// shark[i] = new Shark(r - 1, c - 1, s, d - 1, z);
map[r-1][c-1] = new Shark(r - 1, c - 1, s, d - 1, z);
}
simulate();
System.out.println(person.eat);
}
public static void simulate() {
//1. 낚시왕이 오른쪽으로 한칸 이동합니다.
while(++person.c < C) {
//2. 낚시 왕이 있는 열에 있는 상어 중에 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
catchShark();
//3. 상어가 이동한다.
sharkMove();
map = new Shark[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if(newMap[i][j] != null)
map[i][j] = new Shark(newMap[i][j].r, newMap[i][j].c, newMap[i][j].moveable, newMap[i][j].dir, newMap[i][j].size);
}
}
}
}
public static void catchShark() {
for(int i=0;i<R;i++) {
if(map[i][person.c] != null) { //하나만 잡아먹습니다.
// System.out.println("i:"+i+"j:"+person.c);
person.eat += map[i][person.c].size;
map[i][person.c] = null;
return ;
}
}
}
public static void sharkMove() {
newMap = new Shark[R][C];
//상하우좌.
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, 1, -1};
for(int row=0; row<R;row++) {
for(int col=0;col<C;col++) {
if(map[row][col] == null) continue;
Shark temp = map[row][col];
int nr = temp.r, nc = temp.c;
//이동할때 r이라면 R ( dx[temp.dir] * temp.moveable ) % ( 2 * (N - 1)) 으로 나눠줍니다.
//이동할때 c이라면 C ( dy[temp.dir] * temp.moveable ) % ( 2 * (C - 1)) 으로 나눠줍니다.
//그리고 나머지값을 직접 이동시킵니다. 이렇게 할경우 10000
int rMoveableCnt = temp.moveable % ( 2 * (R - 1));
int cMoveableCnt = temp.moveable % ( 2 * (C - 1));
if(temp.dir == 0 || temp.dir == 1) {
for(int movecnt = 0; movecnt<rMoveableCnt;movecnt++) {
nr += dx[temp.dir];
if(nr < 0) {
temp.dir = changeDir(temp.dir);
nr = 1;
}
if(nr >= R) {
temp.dir = changeDir(temp.dir);
nr = R - 2;
}
}
}
if(temp.dir == 2 || temp.dir == 3) {
for(int movecnt = 0; movecnt<cMoveableCnt;movecnt++) {
nc += dy[temp.dir];
if(nc >= C) {
temp.dir = changeDir(temp.dir);
nc = C - 2;
}
if(nc < 0) {
nc = 1;
temp.dir = changeDir(temp.dir);
}
}
}
temp.r = nr;
temp.c = nc;
//만약 이동한 칸에 상어가있따면 크기를 비교하여 서로 잡아먹도록합니다.
if(newMap[nr][nc] != null) {
Shark before = newMap[nr][nc]; //미리 도착한 상어.
if(before.size < temp.size ) { //만약 새로운게 더 크다면,
newMap[nr][nc] = new Shark(temp.r, temp.c, temp.moveable, temp.dir, temp.size);
map[row][col] = null; //이렇게하면 연결된 것까지 사라진다.
}
}else if(newMap[nr][nc] == null) {
newMap[nr][nc] = new Shark(temp.r, temp.c, temp.moveable, temp.dir, temp.size);
map[row][col] = null;
}
}
}
}
public static int changeDir(int dir) {
if(dir == 0) {
return 1;
}else if(dir == 1) {
return 0;
}else if(dir == 2) {
return 3;
}else if(dir == 3) {
return 2;
}
return -1;
}
}
class Person{
int c;
int eat;
public Person(int c, int eat) {
this.c = c;
this.eat = eat;
}
}
class Shark{
int r;
int c;
int size;
int dir;
int moveable;
boolean dead = false;
public Shark(int r, int c, int moveable, int dir, int size) {
this.r = r;
this.c = c;
this.moveable = moveable;
this.dir = dir;
this.size = size;
}
}
처음에 Shark배열을 활용해서만 진행한경우.
시간초과가 예상된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int R, C, M, N;
public static int[][] arr;
public static Shark[] shark;
public static Shark[][] map;
public static Person person;
public static int answer = 0;
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());
person = new Person(-1, 0);
arr = new int[R][C];
shark = new Shark[M];
map = new Shark[R][C];
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
shark[i] = new Shark(r - 1, c - 1, s, d - 1, z);
}
}
public static void simulate() {
while(person.c < C) {
//1. 낚시왕이 오른쪽으로 한칸 이동합니다.
person.c += 1;
//2. 낚시 왕이 있는 열에 있는 상어 중에 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
catchShark(person.c);
//3. 상어가 이동한다.
sharkMove();
sharkEat();
}
}
public static boolean catchShark(int personC) {
//현재
int personR = 0;
while(personR < N) {
for(int i=0; i<M;i++) {
if( shark[i].r == personR && shark[i].c == personC && shark[i].dead == false) {
shark[i].dead = true;
person.eat += shark[i].size;
return true;
}
}
personR+=1;
}
return false;
}
public static boolean sharkMove() {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, 1, -1};
for(int i=0; i<M;i++) {
Shark temp = shark[i];
int r = temp.r;
int c = temp.c;
//이동할때 r이라면 R ( dx[temp.dir] * temp.moveable ) % ( 2 * (N - 1)) 으로 나눠줍니다.
//이동할때 c이라면 C ( dy[temp.dir] * temp.moveable ) % ( 2 * (C - 1)) 으로 나눠줍니다.
//그리고 나머지값을 직접 이동시킵니다. 이렇게 할경우 10000
//상, 하 로 이동하는경우입니다.
if(temp.dir == 0 || temp.dir == 1) {
//앞으로 남은 이동해야하는 횟수
int rMoveableCnt = ( temp.moveable ) % ( 2 * (R - 1) );
int nr = temp.r;
for(int move = 0; move < rMoveableCnt; move++) {
nr += dx[temp.dir];
if(nr == (R - 1) || nr == 0) {
temp.dir = changeDir(temp.dir);
}
}
temp.r = nr;
}
//상, 하 로 이동하는경우입니다.
else if(temp.dir == 2 || temp.dir == 3) {
int nc = temp.c;
int cMoveableCnt = ( temp.moveable ) % ( 2 * (C - 1) );
for(int move = 0; move < cMoveableCnt; move++) {
nc += dx[temp.dir];
if(nc == (C - 1) || nc == 0 ) {
temp.dir = changeDir(temp.dir);
}
}
temp.c = nc;
}
}
}
public static int changeDir(int dir) {
if(dir == 0) {
return 1;
}else if(dir == 1) {
return 0;
}else if(dir == 2) {
return 3;
}else if(dir == 3) {
return 2;
}
return -1;
}
}
class Person{
int c;
int eat;
public Person(int c, int eat) {
this.c = c;
this.eat = eat;
}
}
class Shark{
int r;
int c;
int size;
int dir;
int moveable;
boolean dead = false;
public Shark(int r, int c, int size, int dir, int moveable) {
this.r = r;
this.c = c;
this.size = size;
this.dir = dir;
this.moveable = moveable;
}
}