[백준 - Java] 17143번 : 낚시왕(삼성 SW 역량 테스트 기출 문제)

문제

www.acmicpc.net/problem/17143

17143번: 낚시왕

 

삼성 SW 역량 테스트 기출문제이다.

문제에서 요구하는대로 구현하면 되는 시뮬레이션 문제이다.

 

구현

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판.

 

낚시왕이 1초에 한 칸씩 열을 이동하며 상어를 잡는다. (가장 오른쪽 열, C칸에 도착하면 이동 멈춤 -> 낚시 종료)

1초 동안 일어나는 조건을 고려해 C초까지 낚시를 하는 것이다!

 

낚시의 조건은 아래와 같고 이를 바탕으로 총 낚시왕이 잡은 상어 크기의 합을 구하는 문제이다!

 

낚시의 조건 

1. 낚시왕이 오른쪽으로 한 칸 이동한다.

 

2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. (낚시왕이랑 가장 가까운, 행 번호 가장 작은 상어 잡으면 됨)

상어를 잡으면 격자판에서 잡은 상어가 사라진다.

 

3. 상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다.

상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한 채로 이동한다.

 

4. 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 

이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

 

-> 낚시왕이 한칸씩(1초씩) 이동하면서 1~4의 행위가 반복된다.

 

 

ex) 아래 그림의 상태에서 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인 경우는 왼쪽을 의미한다.
두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

 

단순히 하나의 값이 아니라 위치, 속력, 방향, 크기 등 여러 값을 가지고 있는 경우라면 클래스 구조체를 만들어 저장하는 편이 좋다!

상어는 r, c, s, d, z 총 5개의 값을 가지고 있다.

상어 클래스를 만들어 5개의 값을 저장할 수 있도록 했다.

 

class Shark {
	int r; // 행 위치
	int c; // 열 위치
	int s; // 속력
	int d; // 방향
	int z; // 크기

	Shark(int r, int c, int s, int d, int z) {
		this.r = r;
		this.c = c;
		this.s = s;
		this.d = d;
		this.z = z;
	}
}

 

격자판의 경우 상어 객체를 저장할 R x C의 2차원 배열로 만들었다.

그리고 이 격자판에 주어진 상어의 정보를 바탕으로 상어 클래스의 인스턴스를 저장했다.

 

r과 c는 1부터 시작되는데 배열에 넣을거라서 r과 c값에 -1을 해주었다.

방향의 경우 상, 하, 좌, 우 -> 1, 2, 3, 4의 값으로 들어오지만 편하게 바꾸기 위해 0, 1, 2, 3으로 바꿔주었다.

 

왜? 방향 바꾸기 팁!

2차원 배열에서 상 하 좌 우 이동해야하는 경우가 알고리즘 문제에서 종종 나온다.

이때 x, y 이동을 편리하게 하기 위해 dx, dy 배열을 만들어 두면 좋다.

 

 

인덱스 0, 1, 2, 3의 순으로 상, 좌, 하, 우라고 외우면 좋다.

위의 그림에서 상은 (-1, 0) 부터 시작하고 반시계 방향으로 우까지 돌아가는 순이다.

이를 배열로 나타내면 아래와 같다. 

 

 

 

예를 들어 현재 2차원 배열의 (2, 2)에 상어가 있다.

여기서 위쪽으로 가려면 (2, 2) + (-1, 0) => (1, 2)

왼쪽은 (2, 2) + (0, -1) => (2, 1)

아래쪽은 (2, 2) + (1, 0) => (3, 2)

오른쪽은 (2, 2) + (0, 1) => (2, 3) 

이런식으로 dx, dy의 방향에 따른 인덱스 값을 현재 좌표 값에 더해서 위치를 간단히 이동시킬 수 있다!

 

 

 

 

추가로 상어는 격자판의 경계를 넘는 경우, 즉 경계 벽을 만나면 방향을 반대로 바꾼다.

방향 반대로 바꾸기는 d' = (d + 2) % 4 로 일일이 방향을 검증해 바꾸지 않고 쉽게 바꿀 수 있다.

 

예를 들어 2번 아래쪽에 있을 경우

(2 + 2) % 4 = 0 위쪽 방향

 

1번 왼쪽 방향에 있을 경우

(1 + 2) % 4 = 3 오른쪽 방향의 값이 나온다.

 

public static int R, C, M;
public static Shark[][] map;

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 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()); // 크기 

		//방향 쉽게 바꾸기위해 입력받은 상하좌우(1 2 3 4) -> 상좌하우(0 1 2 3)로 변경 
		if(d == 1)
			d = 0;
		else if(d == 4)
			d = 1;

		map[r-1][c-1] = new Shark(r-1, c-1, s, d, z); //격자판에 상어 저장 
	}
    
}

 

낚시 시작

낚시왕이 1초에 한 칸씩 열을 이동하며 상어를 잡는다. (가장 오른쪽 열, C칸에 도착하면 이동 멈춤 -> 낚시 종료)

-> for문을 이용해 열의 끝까지 반복한다.

 

1. 낚시왕이 오른쪽으로 한 칸 이동한다.

-> 0번 열부터 시작해 col 변수가 1씩 증가하며 낚시왕이 이동한 것으로 간주한다.

 

for(int col = 0; col < C; col++) {

}

 

2. 낚시왕이 있는 열에서,  행 번호가 가장 가까운 상어를 잡는다. 

-> for문을 통해 각 열에 해당하는 행을 차례로 돌면서 가장 가까운(가장 먼저 null이 아닌) 상어를 찾는다.

-> 찾았다면 answer 정답 변수의 그 상어의 크기를 더한다. (처음엔 answer = 0)

 

상어를 잡으면 격자판에서 잡은 상어가 사라진다.

-> 격자판 map의 값에 null값을 주어 상어가 잡혔다는 의미로 없앴다.

 

// 1. 낚시왕 이동 
for(int row = 0; row < R; row++) {
	if(map[row][col] != null) { 
		answer += map[row][col].z; // 2. 가장 가까운 상어 크기 정답 변수에 저장 
		map[row][col] = null; //map에서 상어 없애기 
		break;
	}
}

 

3. 상어가 이동한다.

-> 큐를 만들어 현재 map에 있는 상어들을 큐에 추가한다.

(기존 맵에서 상어를 하나하나 이동시키고 이동된 위치에 상어가 있는지 없는지, 크기가 어떤지를 비교하는 것보다

차라리 현재 잡히지 않고 남아있는 상어를 바탕으로 새롭게 맵을 구성하는 편이 더 낫기 때문에 만든 큐)

-> 상어들이 이동된 새로운 맵을 만들기 위해 맵을 초기화 해준다.

-> 큐에서 상어를 한 마리씩 꺼내서 큐가 빌 때까지 상어를 이동시킨다.

 

// 3. 상어 이동 
Queue<Shark> queue = new LinkedList<>(); 
for(int i = 0; i < R; i++) {
	for(int j = 0; j < C; j++) {
		if(map[i][j] != null) { // 현재 map에 있는 상어들 큐에 추가 
			queue.add(new Shark(i, j, map[i][j].s, map[i][j].d, map[i][j].z));
		}
	}
}

map = new Shark[R][C]; // 새로운 낚시판 만들기위해 배열 초기화 

// 모든 상어 한마리씩 꺼내서 이동 
while(!queue.isEmpty()) {
	Shark sm = queue.poll();

    // 속력만큼 상어 이동 시키기 - 아래에서 구현 
}

 

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 

-> 속력은 최대 1000까지 주어지는데 속력만큼 한 칸 한 칸 이동시키면 굉장히 비효율적! 시간 초과 난다!!

-> 최소한의 이동을 위해 속력을 나머지 연산을 해준다.

 

 

예를 들어 열 3번 칸에서 왼쪽 방향으로 움직이는 상어 C는 8의 속력으로 이동한다면

이동 후에는 열 5번 칸에 오른쪽 방향을 보는 상어로 바뀌어 있을 것이다. (이동하다 벽 만나서 방향 바꿨으니까)

 

이 상어가 다시 3번 칸에 같은 방향으로 오려면 몇의 속도로 이동하면 될까?

10의 속도로 이동한다면 기존의 상어 모습과 동일하게 이동될 수 있다.

 

 

즉, 총 열의 개수인 C 값, 6칸만큼을 2배로 이동한다면 제자리에 같은 방향으로 이동될 수 있다는 것이다.

이를 이용해 제자리로 돌아오는 값을 나누어 그 나머지만큼만 움직인다면 최소한으로 움직일 수 있다.

 

상, 하로 움직이는 상어라면 R 행의 최대 칸의 2배 -> (R - 1) * 2 //-1 해준 이유는 map은 1칸이 아니라 0칸부터 시작하기 때문

좌, 우로 움직이는 상어라면 C 열의 최대 칸의 2배 -> (C - 1) * 2

만큼 이동한다면 제자리로 돌아올 수 있다.

속력을 이 값으로 나누어준다면 최소한으로 이동할 할 수 있다.

 

이렇게 최소한으로 움직일 속력을 구한 뒤 이를 기반으로 상어를 이동시킨다.

 

// 속력만큼 상어 이동 시키기 
int speed = sm.s; // 시간초과로 최소한의 이동을 위해 나머지 연산
if(sm.d == 0 || sm.d == 2) // 상 하
	speed %= (R -1) * 2; 
else if(sm.d == 1 || sm.d == 3) // 좌 우
	speed %= (C -1) * 2;

 

-> 구해진 최소한의 속력만큼 for문을 돌며 상어를 한 칸 한칸 이동시켜준다.

-> 위의 입력 부분에서 방향 이동에 대해 설명했듯이,

     각 방향에 맞는 dx, dy 배열의 값을 현재 상어의 r, c에 더해 새로운 이동할 위치를 구해준다.

 

상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한 채로 이동한다.

-> 1칸 이동한 새로운 위치가 범위를 벗어나 벽에 부딪힌다면 방향을 반대로 바꿔준다.

 

for(int s = 0; s < speed; s++) {
	// 현재 r, c에 방향에 맞게 1칸씩 추가하며 위치 이동 
	int newR = sm.r + dx[sm.d]; 
	int newC = sm.c + dy[sm.d];
     
    // 이동할 새로운 위치가 범위를 벗어나 벽에 부딪히면 
	if(newR < 0 || newR >= R || newC < 0 || newC >= C) {
		sm.r -= dx[sm.d]; // 다시 값 돌려주고 
		sm.c -= dy[sm.d];
		sm.d = (sm.d + 2) % 4; // 방향 반대로 
		continue;
	}

	// 위치 벗어나지 않을때는 새로운 위치로 이동 
	sm.r = newR; 
	sm.c = newC;
}

 

4. 이동후 한 칸에 상어가 두 마리 이상 있는 경우, 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

-> 이동을 완료한 바뀐 상어의 위치에 이미 다른 상어가 있는지 확인한다.

-> 있다면 크기 비교 후 큰 경우만 현재 상어를 map에 넣어준다.

-> 없다면 바로 넣어줌 

 

// 4. 새로운 위치가 빈 공간인지 이미 상어가 있는지 확인
if(map[sm.r][sm.c] != null) { // 이미 상어가 있다면 두 상어 크기 비교 
	if(map[sm.r][sm.c].z < sm.z) { // 기존 상어보다 현재 상어가 크다면 
		map[sm.r][sm.c] = new Shark(sm.r, sm.c, sm.s, sm.d, sm.z); // 현재 상어 넣어줌 
	} 
} else { // 없다면 현재 상어 바로 넣어줌 
	map[sm.r][sm.c] = new Shark(sm.r, sm.c, sm.s, sm.d, sm.z);
}

전체 코드

/**
 * @author Minha Gwon
 * 2020. 10. 12.
 * URL : https://www.acmicpc.net/problem/17143
 * BOJ#17143 - 낚시왕 
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int R, C, M;
	public static Shark[][] map;
	public static int answer = 0;
	public static int dx[] = {-1, 0, 1, 0}; //상 좌 하 우 순 
	public static int dy[] = {0, -1, 0, 1};

	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 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()); // 크기 
 
			// 방향 쉽게 바꾸기위해 입력받은 상하좌우(1 2 3 4) -> 상좌하우(0 1 2 3)로 변경 
			if(d == 1)
				d = 0;
			else if(d == 4)
				d = 1;
            
			map[r-1][c-1] = new Shark(r-1, c-1, s, d, z); // 격자판에 상어 저장 
		}

		
		for(int col = 0; col < C; col++) { // 열의 끝까지 반복 
			// 1. 낚시왕 이동 
			for(int row = 0; row < R; row++) {
				if(map[row][col] != null) { 
					answer += map[row][col].z; // 2. 가장 가까운 상어 크기 정답 변수에 저장 
					map[row][col] = null; // map에서 상어 없애기 
					break;
				}
			}

			// 3. 상어 이동 
			Queue<Shark> queue = new LinkedList<>(); 
			for(int i = 0; i < R; i++) {
				for(int j = 0; j < C; j++) {
					if(map[i][j] != null) { // 현재 map에 있는 상어들 큐에 추가 
						queue.add(new Shark(i, j, map[i][j].s, map[i][j].d, map[i][j].z));
					}
				}
			}

			map = new Shark[R][C]; // 새로운 낚시판 만들기위해 배열 초기화 

			// 모든 상어 한마리씩 꺼내서 이동 
			while(!queue.isEmpty()) {
				Shark sm = queue.poll();
                
				// 속력만큼 상어 이동 시키기 
				int speed = sm.s; // 시간초과로 최소한의 이동을 위해 나머지 연산
				if(sm.d == 0 || sm.d == 2) //상 하
					speed %= (R -1) * 2; 
				else if(sm.d == 1 || sm.d == 3) //좌 우
					speed %= (C -1) * 2;
				
				for(int s = 0; s < speed; s++) {
					// 현재 r, c에 방향에 맞게 1칸씩 추가하며 위치 이동 
					int newR = sm.r + dx[sm.d]; 
					int newC = sm.c + dy[sm.d];

					// 이동할 새로운 위치가 범위를 벗어나 벽에 부딪히면 
					if(newR < 0 || newR >= R || newC < 0 || newC >= C) { 
						sm.r -= dx[sm.d]; // 다시 값 돌려주고 
						sm.c -= dy[sm.d];
						sm.d = (sm.d + 2) % 4; // 방향 반대로 
						continue;
					}

					// 위치 벗어나지 않을때는 새로운 위치로 이동 
					sm.r = newR; 
					sm.c = newC;
				}

				// 4. 새로운 위치가 빈 공간인지 이미 상어가 있는지 확인
				if(map[sm.r][sm.c] != null) { // 이미 상어가 있다면 두 상어 크기 비교 
					if(map[sm.r][sm.c].z < sm.z) { // 기존 상어보다 현재 상어가 크다면 
						map[sm.r][sm.c] = new Shark(sm.r, sm.c, sm.s, sm.d, sm.z); // 현재 상어 넣어줌 
					} 
				} else { // 없다면 현재 상어 바로 넣어줌 
					map[sm.r][sm.c] = new Shark(sm.r, sm.c, sm.s, sm.d, sm.z);
				}
			}
		} // 이동 for문 끝 

		System.out.println(answer);
	}
}

//상어 정보를 저장할 상어 클래스 
class Shark {
	int r;
	int c;
	int s;
	int d;
	int z;

	Shark(int r, int c, int s, int d, int z) {
		this.r = r;
		this.c = c;
		this.s = s;
		this.d = d;
		this.z = z;
	}
}