낚시왕

문제복기 다시 풀어봐도 멘붕인 문제를 어떻게 접근하고, 풀었는지, 어디까지 생각하고 구현 완료했는지, 틀렸다면 어디서 틀렸는지 정확하게 분석하기. 다음번에 풀면 무조건 맞추도록. 기억력에 의존하는 게 아니라. ⭐️ 변수이름 설정할 때 문제에서 주어진 이름 최대한 그대로 가져가기! 이름에 차이가 생기면 혼동된다! 상어클래스 생성할 때 내가 변수이름을 따로 만들어서 속력, 방향, 크기를 입력 받았는데 생성자로 값을 넣어주는 과정에서 순서가 바뀌어서 오답이 출력됨!! 크기값이 속력으로 들어가는 등 입력값이 뒤죽박죽으로 얽혀버림. 또한, R,C,M 등의 변하지않는 절대적인 변수도 대문자로 선언해서 변하는 변수(소문자)들과 헷갈리지 않도록 한다!! Map 같은 것도 대문자로 "Map"으로 설정하기!

핵심⭐️⭐️⭐️⭐️⭐️ 상하 = 좌우 같은 맥락이기 때문에 상하 이동하는 경우를 따져본다.

델타 어레이(dx={-1,1,0,0}, dy={0,0,1,-1}) 활용 => 코드 간결해진다. 현재 상어의 방향에 따라 nr(nc)값이 달라진다. 2중 for문 내에 현재 상어 curr의 다음 이동 위치 하 : nr = i + s; 또는 상 : nr = i-s; 이다. =>현재 상어의 방향에 따라 s값을 덧셈 뺄셈하기 때문에 =>nr = i + s*dx[currr.d] 좌우로 이동하는 경우 r값은 불변이다. 이 경우 좌우는 dx값이 모두 0이기 때문에 s*dx[curr.d] = 0이고, 결국 nr = i + 0 = nr = i로 불변하게 된다.
위로 범위 초과=>아래로 방향 전환했는데도 아래로 또 범위 초과하는 경우 처리 : 몫과 나머지 이용 위로 범위 초과 : -1 곱한다, 아래로 방향 전환. 아래 범위 초과 부분에서 연속해서 계속 범위 초과하는 처리한다! R-1 을 주기로 규칙성을 갖기 때문에 몫과 나머지 연산을 생각해볼 수 있다. 몫 = 현재위치 / (R-1) , 나머지 = 현재위치 % (R-1) 몫이 짝수인 경우, 방향은 그대로 아래방향이다. 시뮬레이션해보면 nr = 나머지 몫이 홀수인 경우, 방향은 위로 전환! nr = (R-1) - 나머지

구현할 로직

낚시왕 오른쪽 1칸 이동 ✅
상어 사냥 : 낚시꾼의 열 위치에서 땅과 가장 가까운 상어를 사냥 ✅🔺
상어 이동. 상어의 다음 위치 구하기🔺 상어가 이동할 때 한칸에 한마리만 있을 수 있다. 2마리 이상인 경우 크기 비교를 통해 큰 놈만 둔다.✅🔺

틀린이유

낚시왕 이동하는 2중 for문에서 배열 인덱스 변수 틀림!! 둘다 소문자라서 헷갈림 주의!=> R,C,M 같은 불변하는 변수(입력데이터)는 대문자로 선언하기! for(int t=0;t<c;t++){ for(int i=0;i<r;i++) { =>map[i][t] 가 되어야하는데 배열 인덱스를 map[r][c]로 해버려서 대실패!!!
상어 사냥 : 낚시꾼의 열 위치에서 땅과 가장 가까운 상어를 사냥. 낚시왕 이동 반복 범위 => for(int t = 0;t<C;t++) 이기 때문에 for(int t = 0;t<C;t++) { for(int i=0;i<R;i++) { i-for문에서 i는 작=>큰 순으로 증가하기 때문에 이것을 통해 자연스럽게 처리된다. 놓친 조건 : 상어 사냥은 한 열에서 한번만 가능하기 때문에 낚시를 한번 하면 break문으로 i-for문을 탈출해야한다.(i-for문 탈출 후에 문제에서 주어진 순서에 따라 로직 구현하면 된다. 사냥 완료 했으니 상어 이동 구현!)
상어 이동. 상어의 다음 위치 구하기.⭐️⭐️⭐️⭐️⭐️ =>RxC 격자판의 모든 상어들을 이동시켜야한다!=>2중 for문으로 구현!! =>소스코드 전체 구조는 아래와 같다!⭐️⭐️⭐️⭐️⭐️

for(int t=0;t<C;t++){//1.낚시꾼 오른쪽 1칸 이
  for(int i=0;i<R;i++){
    //2.상어 사냥
  }
  //3.상어 이동
  for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
      ...
    }
  }
}

내가 구현한 상어 이동

상어가 이동할 때마다 map을 갱신한다. => 이전 map을 기준으로 비교, 갱신하기 때문에 2개의 2차원 map이 필요하다!
일단 문제에서 상어는 방향과 속력을 갖는다고 했기 때문에 상어가 1초 후에 이동하는 위치를 손으로 시뮬레이션해봄으로써 상어가 이동하는 다음위치를 정확하게 이해하는 것이 중요했다.

3. 시뮬레이션 해보면, 일단 상하로 이동하는 경우를 생각해본다. 상어의 다음 r값을 nr라고 하자. c는 고정되있고, nr값은 R의 범위 내에서 이동해야한다. 시뮬레이션 해보면 R-1 을 주기로 방향이 바뀌는 것을 알 수 있었다. => 자연스럽게 속력을 (R-1)로 나누어보는 생각을 한다. 몫과 나머지를 어떻게 이용할 수 있나?

두가지 경우로 나뉜다.

첫번째 시도 🔺 상하로 움직이는 경우, 상 따로 하 따로 구현했다. 그런데 상으로 가다가도 방향이 하로 바뀌고, 하로 가다가 방향이 상으로 바뀐다.

아래 방향, 아래로 범위 초과하는 경우 로직은 대부분 맞았다. 하지만 위 방향, 위로 범위 초과하는 경우에, 방향 아래로 전환, nr 셋팅 후에 또 범위 초과하는 경우 처리하지 못한다. row = 3, s = 7 : nrr = 3-7 = -4 if(nr<0)에 의해 방향은 아래로 전환되지만, nr = s % (R-1) = 7 % 3 = 1. nr = 1이된다. 하지만 실제로 이동해야하는 nr값은 2이다. 3➡2(1번)➡1(2번)➡0(3번)➡1(4번)➡2(5번)➡3(6번)➡2(7번) ⭐️ 다시 if-else문으로 적절히 케이스처리해줘야한다.

Solution ⭐️ 위로 방향 초과하는 애들은 -1을 곱해주면 된다! (아래 그림1 참고) 하지만 -1을 곱해줘도 그래도 아래로 범위초과하는 경우가 문제다.(아래로 방향전환한 경우에도 아래로 범위초과하는 경우) ⭐️-1 곱하고, 아래방향으로 바꿔서 아래 방향 범위초과 처리하는 부분에서 2번 다 초과하는 경우 처리한다! ⭐️몫과 나머지를 이용하기 : 나머지는 이용했는데 몫을 이용하지 못했다.🔺 몫이 짝/홀인지에 따라 이동하는 방향이 다르다! (아래 그림2 참고) ⭐️다음 이동 좌표 : 델타 Array(dx = {-1,1,0,0}, dy={0,0,1,-1}) 이용해서 모든 방향에 대해 일반화할 수 있다! nx = x + dx[i] 응용 nx = x + s * dx[curr.d];//현재의 x위치에서 속력에 방향벡터를 곱한 것을 더해주면 다음 이동할 nx가 된다. =>좌우로 이동하는 경우, nx값은 고정이기 때문에 변하지 않는다. dx[curr.d]는 0이 되기 때문에 nx = x가 된다.

//상하.
if(dir == 0) {//상.
	nx = row-s;//velo = 2, row = 0. 0-2 = 음수!
							
	if(nx<0) {
		dir = 1;
		int tmp = s % (R-1);
		nx = tmp;//nx가 위로 초과하는 경우 방향 아래로 전환, 속력 % (R-1)이 nx 가 된다고 생각함.
	}
}
if(dir == 1) {//하.
	nx = row+s;//row=0,velo=5. 0+5 = 양수, 범위초과!
							
	if(nx>=r) {
		dir = 0;//방향전환.
		int tmp = s % (R-1);
		nx = (R-1) -tmp;
	}
}

두번째 시도 ❌

//상하.
if(dir == 0) {//상.
	nx = row-velo;//velo = 2, row = 0. 0-2 = 음수!
							
	if(nx<0) {
		dir = 1;
		nx = velo % r;
	}
}
if(dir == 1) {//하.
	nx = row+velo;//row=0,velo=5. 0+5 = 양수, 범위초과!
							
	if(nx>=r) {
		dir = 0;//방향전환.
		nx = velo % r;
	}
}

오답 코드 :

package ss;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class FishingKing {
	static int r,c,m,sum;
	static Shark[][] map;
	static class Shark{
		int size,dir,velo;
		Shark(int size,int dir,int velo){
			this.size = size;
			this.dir = dir;
			this.velo = velo;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		r = Integer.parseInt(input[0]);
		c = Integer.parseInt(input[1]);
		m = Integer.parseInt(input[2]);
		System.out.println("r: "+r);
		System.out.println("c: "+c);
		System.out.println("m: "+m);
		//상어 위치 정보 어떻게 저장할 수 있을까.=>2차원 상어맵! 
		map = new Shark[r][c];
		//상어 갯수 m개만큼 5개 정수 입력받는다!!!
		for(int i=0;i<m;i++) {
			input = br.readLine().split(" ");
			for(int j=0;j<5;j++) {
				int x = Integer.parseInt(input[0])-1;
				int y = Integer.parseInt(input[1])-1;
				int velo = Integer.parseInt(input[2]);
				int dir = Integer.parseInt(input[3])-1;
				int size = Integer.parseInt(input[4]);
				map[x][y] = new Shark(size,dir,velo);
			}
		}
		sum=0;//잡은 상어 크기 합.
		for(int t=0;t<c;t++) {//t=낚시왕.1.낚시왕 오른쪽으로 1칸씩 이동.
			for(int i=0;i<r;i++) {//이건 왜 있는 거지.
				//2.낚시왕 열에 상어 있으면 땅과 가장 가까운 상어 잡는다!!
				if(map[r][c]!=null) {
					sum += map[r][c].size;//(0,0)에 없고 (1,0)에 있으면 못 잡고 반복문 지나가는 거 아닌가?
					map[r][c] = null;
				}
				//continue;
				//3.상어 이동!
				//상어 이동전에 백업 map 생성!
				Shark[][] backup = new Shark[r][c];
				for(int j=0;j<r;j++) {
					for(int k=0;k<c;k++) {
						backup[j][k] = map[j][k];
					}
				}
				//본격 상어 이동
				for(int row = 0;row<r;row++) {
					for(int col = 0;col<c;col++) {
						Shark cur = map[row][col];
						
						int dir = cur.dir;
						int velo = cur.velo;
						int size = cur.size;
						
						int nx=0;int ny=0;
						//상하.
						if(dir == 0) {//상.
							nx = row-velo;//velo = 2, row = 0. 0-2 = 음수!
							
							if(nx<0) {
								dir = 1;
								nx = velo % r;
							}
						}
						if(dir == 1) {//하.
							nx = row+velo;//row=0,velo=5. 0+5 = 양수, 범위초과!
							
							if(nx>=r) {
								dir = 0;//방향전환.
								nx = velo % r;
							}
						}
						//오른쪽2, 왼쪽3.
						if(dir == 2) {
							ny = col+velo;
							if(ny>=c) {
								dir = 3;
								ny = velo % c;
							}
						}
						if(dir == 3) {
							ny = col-velo;
							if(ny<0) {
								dir = 2;
								ny = velo % c;
							}
						}
						//상어 위치 겹치는 경우 처리.
						if(backup[nx][ny]!=null && backup[nx][ny].size<cur.size) {
							map[nx][ny] = cur;
						}
						
					}
				}
			}
			continue;//낚시왕 다음 열로 한칸 이동해라!
		}//낚시왕 이동 t-for문!
	}

}

2번째 풀었을 때(2021.10.08금) 맞은 부분 낚시왕 이동✅ 낚시왕이 상어 잡을 때 반복문 스코프&종료 처리✅ 상어 이동 반복문 스코프✅

틀린 부분

2차원 객체 타입 배열에서 상어를 이동시킬 때, 상어가 추가되고 삭제된다. 이 때 이동하기 전의 상어와 이동하고 난 후의 상어가 섞이기 때문에 가장 일반적인 방법으로 동일한 2차원 객체 배열을 하나 생성해서 복사하는 것이다! => 2차원 배열이 하나 더 필요하지 않을까 생각해서 메모리 확인 결과 512MB로 지레짐작했을 때 넉넉한 것 같았다. 근데 2차원 배열을 굳이 하나 만들어야하는 수고로움이 크게 느껴져서 2차원 배열을 하나 더 만들지 않고도 풀 수 있는 방법을 연구했다. M개의 상어 객체를 저장하는 1차원 배열을 생성&상어 정보 저장하고, M개의 상어 각각 위치값 업데이트 시키고 난 후, 문제는 객체 타입 2차원 배열의 업데이트였다. M-for문 내에서 cur.x, cur.y와 nx,ny가 존재=> SharkMap[nx][ny] = cur; 이런 식으로 처리하면 안 되나?! 원래 배열SharkMap을 tmpArr에 복사하고 난 후, SharkMap에는 이동한 후의 상어 객체를 넣어준다! 따라서 현재 상어의 정보는 SharkMap이 아니라 tmpArr에서 조회해야하고, 상어이동처리를 위한 2중 for문을 돌면서, 현재 상어의 위치는 (i,j)이다. (x,y)가 아니라! => 상어 정보는 객체 타입으로 2차원 배열에 저장하기 때문에 (x,y)필요 없이 속도, 방향, 크기 3가지 정보만 있으면 된다! 따라서 상어 클래스에도 이 3가지 속성값만 필요할 뿐이다. 근데 내가 무슨 정신으로 x,y도 속성으로 정의해놔서 에러가 나지 않았고, 올바른 위치인 (i,j)가 아니라 아무 값도 없는 cur.x , cur.y 값을 가져와서 오답이 되었다.
2차원 배열 데이터 타입 : List❌ 상어 객체⭕️ => 상어는 이동한 후를 제외하고, 한 칸에 1마리만 존재한다. 이동 후에는 1칸에 2마리 이상 존재할 경우 바로 처리하기 때문에 1칸에는 반드시 1마리의 상어만 존재한다. 따라서 List 타입이 아니라 상어 객체 타입의 2차원 배열로 하는 것이 적합하다. (어쩐지 List타입으로 get(0)을 하는 것이 매우 번거로웠다. 상어가 1마리 존재한다는 것을 아는데도 get(0)으로 구체적으로 요소 하나를 조회하는 것은 효율적이지 않다.)
nx,ny의 방향 전환 해주는 부분 다 까먹어버렸다. 실컷 nx,ny값 다 구해놓고, nx(ny)<0일 때, R-1(C-1)로 나눴을 때 홀수 일 때, 방향전환이 일어나는데 코드로 구현을 안해버렸다.... ⭐️구현해야하는 로직을 명확하게 필기해서 빠짐없이 구현하도록 하자!노트테이킹, 손코딩의 중요성 규칙성을 발견해서 위치값은 잘 정해주었다. nx(ny)가 음수일 때, -1을 곱해서 양수로 만들어주고, nx>R-1(ny>C-1)인경우에서 다 처리했다.
이동 후 상어 저장할 때 로직 구현 : 새로운 배열 하나 더 생성함으로써 (nx,ny)에 상어가 있는지 없는지(null인지 아닌지)만 판단해서 크기 비교해 주면 된다. (nx,ny)가 null이거나 null이 아니면 size속성값 대소 비교를 통해 현재 상어가 더 큰 경우에만 (nx,ny)에 현재의 상어 객체 넣어주면 된다.
```
if(SharkMap[nx][ny] == null||SharkMap[nx][ny]!= null && SharkMap[nx][ny].size<size) {
  SharkMap[nx][ny] = cur;
}
```

Previous아기 상어 Next컨베이어 벨트

Last updated 3 years ago