.png)
문제
낚시왕이 상어 낚시를 하는 곳은 크기가 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인 경우는 왼쪽을 의미한다.
두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.
출력
낚시왕이 잡은 상어 크기의 합을 출력한다.
✨ Methodology
문제를 읽고 내가 생각해 낸 풀이 방법
1. 상어 클래스
상어 클래스를 별도로 만들어서 입력을 받을 때, M 개의 상어의 정보를 배열에 저장한다.
public static class Shark{
int r;
int c;
int speed;
int direction;//1상2하3우4좌
int size;
//초기 initializing
public Shark(int r, int c, int speed, int direction, int size) {
this.r =r;
this.c = c;
this.speed= speed;
this.size = size;
this.direction = direction;
}
}2. 배열 방향
문제에서, d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다 라고 제시되어 있기 때문에, Direction 배열은 2차원 배열로 "상,하,우,좌" 로 만든다.
static int[][] dd= {{0,0},{-1,0},{1,0},{0,1},{0,-1}};//상하우좌방향을 바꿀때에는,
if previous direction : 상(1) -> 하로 바꿔야 함->2 (+1)
if previous direction : 하(2) -> 상으로 바꿔야 함->1 (-1)
if previous direction : 우(3) -> 좌로 바꿔야 함 ->4 (+1)
if previous direction : 좌(4) -> 우로 바꿔야 함 ->3 (-1)
위처럼 직접 쓰고 나면 규칙성을 찾을 수 있다.
따라서, 짝수 direction -> -1, 홀수 direction -> +1 해주면 방향이 반전된다.
3. 상어의 예상 이동 위치
개인적으로 이 문제는 시뮬레이션부터 돌리면 안된다고 생각한다.
만약, 2번째 상어를 이동시켰는데 이동시킨 지점에 아직 이동시키지 않은 3번째 상어가 있다면 이와 관련된 처리가 골치아프기 때문이다. 따라서, 내가 생각해낸 방식은 앞서 만든 Shark 형의 리스트에 저장된 위치만 미리 상어의 위치를 전부 계산한 후에 시뮬레이션을 돌리는 방식이다.
따라서, 미리 리스트에 상어의 새 좌표를 업데이트 하고 상어의 예상 이동 위치를 계산할 때에는, 배열의 범위에서 벗어날때에만 신경쓰면 된다.
변수
int move = sharks.get(i).speed;// 상어는 speed 만큼 움직인다
int nr = sharks.get(i).r;//row 좌표를 계산할 변수
int nc = sharks.get(i).c;//col 좌표를 계산할 변수
상어는 1초 마다 speed 만큼 움직일 수 있다. 따라서, 1 초동안 move변수에 상어가 움직이는 칸의 횟수 (speed)를 저장하고 speed를 while 문에서 감소시켜주면서 움직일 수 있는 기회가 0이 될때까지 nr과 nc를 계산한다.
while 문
상어는 1초동안 위에서 선언한 move 만큼 좌표를 이동해야 한다.
상어는 한번 이동할 때 마다
nr += dd[sharks.get(i).direction][0];
nc += dd[sharks.get(i).direction][1];만큼 움직인다. shark.get(i).direction은 상어의 이동 방향이기 때문에, dd[방향][0]은 r좌표, dd[방향][1]은 c의 좌표가 된다. 이동이 끝난 후 nr 과 nc의 범위를 확인해서 만일 nr과 nc의 범위가 배열을 벗어난다면, 움직여서는 안되는 칸을 이미 움직여버렸기때문에, 방향을 바꾸어서 두칸 이동하면 된다.
//움직이고 난 후에 범위가 넘었을 경우:
if(nr<1||nc<1||nr>=R+1||nc>=C+1) {
//방향 전환:
if(sharks.get(i).direction%2 ==0){sharks.get(i).direction-=1;}
else{sharks.get(i).direction+=1;}
//이미 움직여버렸기때문에 반대 방향으로 두칸 이동해줘야함
nr += dd[sharks.get(i).direction][0]*2;
nc += dd[sharks.get(i).direction][1]*2;
}이동이 끝난 후엔 마지막으로 업데이트 된 nr,과 nc값을 상어에게 적용시켜 주면 된다.
4. 시뮬레이션
상어의 위치 배열이 업데이트 되었다면, 맵을 초기화 시켜준 다음 리스트에 저장된 상어들을 제 위치에 풀어주면 된다.
배열에는 상어의 index를 저장해야 사이즈를 쉽게 비교할 수 있고, 후에 낚시꾼이 어떤 상어를 잡았는지 쉽게 풀이할 수 있다. index번호가 아니라 상어의 사이즈를 넣는다면, 후에 더 큰 상어가 같은 자리에 오게 되었을 경우에 수정할수없는 불상사가 발생한다...
이때, 상어를 풀려는 자리에 이미 상어가 있다면 둘의 사이즈를 비교해서 더 작은 상어는 배열의 (0,0)으로 이동 시키고 리스트에 상어의 위치를 (0,0)으로 업데이트 시켜준다.
리스트에서 삭제하지 않는 이유는, 처음에 리스트에서 삭제 한 후 index--, i++등 처리를 해주었으나, 백준의 마지막 테스트 케이스에서 문제가 발생하는걸 보게되었다.
상어를 리스트에서 빼게 될 경우, 상어의 인덱스가 줄어들기 때문에 배열에 인덱스가 2인 상어가 두마리가 찍히는걸 보게되었다. 따라서, 상어를 리스트에서 없애는 방식이 아니라 해당 상어를 배열 밖으로 보내는 방법을 택했다.
배열의 (0,0)으로 이동시켜주었기 때문에, 앞서 말한 상어의 예상 위치 메서드에서
if(nr == 0 || nc==0) continue outer; 처리를 해주면, 다음 상어로 넘어간다. 만약 이 처리를 해주지 않는다면 상어를 -1로 옮겨서 array index out of bound 에러가 발생할 수 있으니 꼭 처리해 줘야한다.
for(int i =1; i<index; i++) {
int r = sharks.get(i).r;//상어의 r 위치
int c = sharks.get(i).c;//상어의 c 위치
//사이즈가 아니라 현재 상어의 인덱스를 넣는다! 사이즈를 넣으면 후에 더 큰 상어가 오면 문제생김
if(arr[r][c]==0) {arr[r][c] = i;}//상어가 없으면 그냥 넣어도 된다
else if(arr[r][c]!=0) { //상어가 이미 있다
if(sharks.get(arr[r][c]).size>sharks.get(i).size){//기존상어가 더 큼
sharks.get(i).c = 0;
sharks.get(i).r = 0;
}
else {//현재 상어가 더 크다!
int eaten = arr[r][c];//잡아먹힌 상어
sharks.get(eaten).c = 0;
sharks.get(eaten).r = 0;
arr[r][c] = i;//큰 상어가 살아 남았다
}
}
}5. 낚시꾼이 잡은 상어
낚시꾼은 총 c(열)초를 움직이게 되는데, t= 1로 놓고 while 루프를 사용하여 t<c가 될때까지 돌리면서 낚시-> 상어 이동-> 맵에 배치 를 반복하면 된다. 또한, 상어가 수영하기 전에 낚시꾼이 먼저 1초에 와있기 때문에, input을 받은 후에 낚시꾼이 먼저 낚시를 해야 한다.
//메인 메서드 내의 틀:
int answer = 0; //상어의 사이즈를 더할 변수
validateLocation();//입력을 받은 직후 상어를 물에 풀어준다
int t = 0; //t는 0부터 시작해서 열(time)과 같아질 때 까지 낚시를 한다
int time = C;//낚시꾼은 열을 이동하며 낚시를 하며, 열의 끝에오면 낚시가끝난다-> time== Column
while(t<time){
t++;//time == 낚시꾼의 위치
answer+=caught(t); //1. 낚시왕이 오른쪽으로 한칸 이동하며 낚시한다
swim(); //2. 상어의 예상 위치 계산
validateLocation();//3. 상어 맵에 배치
}낚시꾼이 t 초에 잡은 상어는, 배열을 돌면서 배열의 arr[i][t초]가 0이 아닐 때, 즉 상어가 존재할 때 그 상어의 크기를 정답에 더하고 상어 리스트에서 잡힌 상어를 제거하면 된다. 또한, 낚시꾼은 가장 t열의 가장 앞에있는 상어만 잡기 때문에 가장 가까이에 있는 상어를 잡으면 탐색을 멈춰야 한다.
/**낚시꾼이 t초에 잡은 상어*/
private static int caught(int t) {
int caught = 0;
for(int i = 1; i <=R; i++) {//C는 고정--as t
if(arr[i][t]!=0) {//가장 가까운 상어 발견 -> arr에는 상어의 index가 저장되어있다
caught= sharks.get(arr[i][t]).size; //상어의 크기 리턴
sharks.remove(arr[i][t]); //상어 리스트에서 상어는 빼준다
arr[i][t] = 0;
return caught;
}
}
return caught;//해당 열에 상어가 없다면 0 리턴
}✨ 전체 소스 코드
MapInfo()와 SharkLocationInfo()는 시뮬레이션 할 때, 상어와 맵의 현재 상황을 더 잘 파악하기 위해 구현한 utility이다. 맵과 상어의 상태를 보고싶으면 주석을 해제하면 된다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 백준_17143_낚시왕 {
public static class Shark{
int r;
int c;
int speed;
int direction;//1상2하3우4좌
int size;
//초기 initializing
public Shark(int r, int c, int speed, int direction, int size) {
this.r =r;
this.c = c;
this.speed= speed;
this.size = size;
this.direction = direction;
}
}
static ArrayList<Shark> sharks;//상어의 정보를 저장할 배열
static int[][] dd= {{0,0},{-1,0},{1,0},{0,1},{0,-1}};//상하우좌
static int R,C,time,arr[][];
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = time = Integer.parseInt(st.nextToken());//time: 총 열만큼 움직이고 마지막 열에서 끝나기 때문에 time== C
int M = Integer.parseInt(st.nextToken());//상어의 수
if(M==0) {System.out.println("0");return;}
arr = new int[R+1][C+1];
sharks = new ArrayList<>();
sharks.add(new Shark(0,0,0,0,0));//dummy data
for(int m = 0; m<M ; m++) {//상어의 수만큼 정보 들어온다
//at 0초:
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());//상어 r 좌표
int c = Integer.parseInt(st.nextToken());//상어 c 좌표
int s = Integer.parseInt(st.nextToken());//speed
int d = Integer.parseInt(st.nextToken());//direction
int z = Integer.parseInt(st.nextToken());//size
sharks.add(new Shark(r,c,s,d,z));
}//end of input
int answer = 0;
int t =0;
validateLocation();//initiate
// MapInfo();
while(t<time) {
t++;
// System.out.println("낚시 start");
answer += caught(t);//낚시꾼이 먼저 잡고
// SharkLocationInfo();
// MapInfo();
// System.out.printf("after %d초: ",t);
// System.out.println("상어가 수영했다");
swim();//상어 이동위치 잡고
// SharkLocationInfo();
// System.out.println("validate 후 맵에 추가");
validateLocation();//상어 옮기고
// SharkLocationInfo();
// MapInfo();
}
System.out.println(answer);
}//end of main
/**3. 낚시꾼이 t초에 잡은 상어*/
private static int caught(int t) {
int caught = 0;
for(int i = 1; i <=R; i++) {//C는 고정--as t
if(arr[i][t]!=0) {//상어가 있다면 그 상어의
//arr[][]에는 상어의 인덱스가 담겨져 있다
caught= sharks.get(arr[i][t]).size;
sharks.remove(arr[i][t]);
arr[i][t] = 0;
return caught;
}
}
return caught;
}
/** 2. 상어를 맵에 배치 :1번 메소드에서 업데이트된 상어 위치를 기반으로,
해당 위치에 상어 두마리 이상인지 확인하고 크기가 큰 상어만 배치한다.*/
private static void validateLocation() {
//배열 초기화:
for(int i= 0 ;i<=R; i++) {
for(int j =0; j<=C ;j++) {
arr[i][j] = 0;
}
}
int index = sharks.size();
for(int i =1; i<index; i++) {
int r = sharks.get(i).r;//상어의 r 위치
int c = sharks.get(i).c;//상어의 c 위치
// System.out.printf("%d , %d 상어 생성\n",r,c);//확인용
if(arr[r][c]==0) {//상어가 없다면 그냥 넣어도 된다
arr[r][c] = i;//사이즈가 아니라 현재 상어의 인덱스를 넣는다! 사이즈를 넣으면 후에 더 큰 상어가 오면 문제생김
}
else if(arr[r][c]!=0) {
// System.out.println("현재 위치에 상어가 이미 있다");
if(sharks.get(arr[r][c]).size>sharks.get(i).size) {
// System.out.println(i+"번째 상어는 퇴출한다 -> 기존애 사이즈가 더 커서 ");
//sharks.remove(i);//작은 상어는 퇴출..하지말고 0,0으로 보내야 문제 발생 x
sharks.get(i).c = 0;//먹힌 상어들의 좌표를 0,0으로 지정
sharks.get(i).r = 0;//먹힌 상어들의 좌표를 0,0으로 지정
}
else {//현재 상어가 더 크다!
int eaten = arr[r][c];//잡아먹힌 상어
sharks.get(eaten).c = 0;//0,0으로 지정
sharks.get(eaten).r = 0;//0,0으로 지정
arr[r][c] = i;//큰 상어가 살아 남았다
}
}
}
//배열 채워짐
}
/**1번 메서드: 상어의 예상 이동 위치를 상어 배열에 업데이트 시킨다.*/
private static void swim() {
outer: for(int i = 0; i< sharks.size() ;i ++) {
//원래 좌표: System.out.printf("Previous Location: %d,%d\n",sharks.get(i).r,sharks.get(i).c);
int move = sharks.get(i).speed;//이만큼 움직여야 한다
int nr = sharks.get(i).r;//새 위치 //row: y좌표
int nc = sharks.get(i).c;//새 위치//col: x좌표
if(nr == 0 || nc==0) continue outer; //먹힌 상어들은 무시하고 다음 i로 이동
while (move>0) {
nr += dd[sharks.get(i).direction][0];//dd[방향][r표시]
nc += dd[sharks.get(i).direction][1];//dd[방향][c표시]
//움직이고 나서:
if(nr<1||nc<1||nr>=R+1||nc>=C+1) {//범위를 넘겼을 경우:
if(sharks.get(i).direction%2 ==0){sharks.get(i).direction-=1;}//짝수일 경우 -1
else{sharks.get(i).direction+=1;}//홀수일 경우 +1
nr += dd[sharks.get(i).direction][0]*2;//이미 움직여서는 안되는 곳까지 움직였기 때문에 반대 방향으로 두칸 이동
nc += dd[sharks.get(i).direction][1]*2;
}
move--;
}
//위 while 끝나면 nx 와 ny 를 다시 상어 위치로 업데이트
sharks.get(i).r = nr;
sharks.get(i).c = nc;
//새 좌표 확인: System.out.printf("new location: %d, %d\n",nr,nc);
}
}
//Utilities
/**상어 리스트에서 남은 상어들의 정보를 확인한다*/
public static void SharkLocationInfo() {
/*상어 위치 정보: */
System.out.println("상어 위치 정보");
System.out.println("+-----------+----------------+------------+");
for(int i =0; i< sharks.size() ; i++) {
System.out.println("index "+i+" : "+ sharks.get(i).r+" , "+sharks.get(i).c);
}
}
/**현재 배열의 상태를 출력한다*/
public static void MapInfo() {
System.out.println("현재 맵: ");
for(int i =1; i<=R; i++) {
for(int j = 1; j<=C; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}//배열 체크
}
}
✨배운점
방향 배열을 좀 더 잘 쓰게 된 것 같다. 처음 생각했던 Methodology에서 벗어나지 않고 코드를 짰는데 이 methodology를 실천하기 위해 처음 생각했던 방식에서 많이 수정해 나갔다.
- 상어의 예상 위치
nr = sharks.get(i).r + dd[sharks.get(i).direction][0]* sharks.get(i).speed 로 풀면 쉽게 풀릴 줄 알았지만, 배열의 범위를 벗어나는 경우를 처리하기 어려워서 정말 많은 수정을 해야 했다.- 백준의 마지막 예제 테스트 케이스 오류
생각한대로 구현 한 후 샘플들을 돌려봤는데, 마지막 테스트 케이스의 출력값이 정답과 다르게 나왔다. 상어를 맵에 배치하는 메서드에서, 잡아먹힌 상어들을 상어 리스트에서 아예 제거했었는데 이로 인해 다음 상어들의 index가 작아지면서 같은 index인 상어들이 배열에 놓이게 된것이다..! 따라서, 상어를 리스트에서 제거하지 않고 (0,0)으로 날려보냈다.- 런타임 에러
모든 실수를 고치고 백준을 돌려봤는데 런타임 에러가 나와서 한참을 해맸다. 상어의 예상 위치 메서드에서 (0,0)으로 위에서 잡아먹힌 상어들의 경우에 speed나 direction을 그대로 유지하고 있기 때문에 -1로 이동하면서 범위를 벗어나서 생긴 에러였다. 이는 (0,0)일때에는 무시하고 다음번 i 일때로 넘어가 주었다.
이번 문제를 풀 때에는 많은 시간이 소요됐는데, 다음에는 풀이 시간을 좀 더 단축하고 싶다
.jpeg)