[백준 17143] - 낚시왕(JAVA)[골드1]

문제

https://www.acmicpc.net/problem/17143

17143번: 낚시왕

 

문제 풀이

문제를 꼼꼼히 잘 읽고 흐름을 파악해서 코드를 작성하면 어려운 문제는 아니라고 생각한다.

 

문제를 풀기 위해 생각해야 할 점은 다음과 같다.

 

1. 낚시가 진행되는 순서(낚시왕 이동, 상어 잡기, 상어 이동)
2. 상어를 움직이는 로직
3. 같은 칸에 있는 상어 처리하기

이렇게 크게 3개라고 생각한다.

 

상어를 움직이는 로직은 다양하게 구현할 수 있다.

낚시가 진행되는 순서

• 낚시가 진행되는 순서대로 작업을 처리해야 한다.
• 즉 낚시를 하고, 상어를 움직이고, 모든 상어가 움직인 뒤  상어가 같은 위치에 있는지 체크를 해줘야 한다.
• 아마 많은 사람들이 개별적인 상어가 움직이고 같은 위치에 있는지 체크를 해서 틀린 경우도 많을 것이다.

낚시하기

정말 간단하게 해당 열에서 행을 이동하면서 가장 가까운 상어를 찾고 해당 크기를 더해주면 된다.

 

상어를 움직이는 로직

초기

상어의 속력만큼 한꺼번에 거리를 계산해서 왕복 횟수와 나머지 연산을 통해서 처리해 주려고 했지만, 굉장히 복잡했다.

 

1. 예를 들어서 상어가 현재 위치에서 갈 수 있는 만큼 이동을 한다.
2. 이동한 거리를 r이나 c로 나눠서 왕복 횟수를 계산한다.
3. 왕복 횟수에 따라 방향이 바뀌었는지를 계산하고, 나머지 연산을 해서 위치를 결정해 준다.

이것도 맞는 방법이지만, 쉬운 방법이 있는데 복잡하게 풀고 있는 것이라고 느낌이 들었다.

 

최종

상어의 속력만큼 반복문을 통해서 상어의 위치를 옮겨주고, 벽을 부딪힐 때마다 위치를 조정하고, 방향을 변경했다.

• 해당 방법으로 하니 코드가 훨씬 직관적이었다.
• 하지만 많은 if문 처리로 가독성이 나빠진 단점이 있다.

흐름에 대해서 간단하게 말하면

1. dir 배열을 통해서 상어의 위치를 s만큼 반복해서 옮겨준다.
2. 열을 움직이고 있다면 열이 0으로 갈 때와 c+1 갈 때에 대해서 처리를 해준다.
   • 0으로 간다면 위치를 2로 옮겨주고, 방향을 반대로 바꿔준다.
     이유는 1에서 0으로 가지 않고 반대방향으로 움직이기 때문
   • c+1로 가는 경우 위치를 c-1로 옮겨주고, 방향을 반대로 바꿔준다.
     이유는 c에서 c+1로 가지 않고 반대방향으로 움직이기 때문
3. 행을 움직일 경우도 동일하다.
   1. 0으로 간다면 위치를 2로 옮겨주고, 방향을 반대로 바꿔준다.
   2. r+1로 간다면 위치를 r-1로 옮겨주고  방향을 반대로 바꿔준다.

 

같은 칸에 있는 상어 먹기

중요한 점은 모든 상어가 움직인 뒤, 같은 칸에 있는지 체크를 해야 한다.

즉 A가 이동하고 B가 이동하는 경우

A가 이동했고, A의 이동이 끝난 시점에서 B가 위치가 일치하지만 잡아먹을 수 없다.

이유는 B도 이동하기 때문이다.

이것을 구현하기 위해서 기존 배열이 아닌 새로운 배열을 만들어줘야 한다.

새로운 배열을 통해서 A 상어를 옮겨주고, B상어가 움직일 경우 A와 위치가 같다면 크기를 비교하고 처리하면 된다.

 

 

 

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int r, c, m;
	static int dir[][] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
	static Shark[][] sharks;
	static int answer = 0;

	public static void main(String[] args) throws IOException {
		input();
		fishing();
		System.out.print(answer);
	}

	public static void input() throws IOException {
		st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		sharks = new Shark[r + 1][c + 1];
		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());
			sharks[r][c] = new Shark(r, c, s, d, z);
		}
	}

	public static void fishing() {
		for (int i = 1; i <= c; i++) {
			Shark find = findsharks(i);
			if (find != null) {
				sharks[find.r][find.c] = null;
				answer += find.z;
			}
			sMove();
		}
	}
	public static Queue<Shark> selectShark() {
		Queue<Shark> q = new LinkedList<Main.Shark>();
		for (int row = 0; row <= r; row++) {
			for (int col = 0; col <= c; col++) {
				if (sharks[row][col] != null) {
					q.add(sharks[row][col]);
				}
			}
		}
		return q;
	}
	public static void sMove() {
		Queue<Shark> q = selectShark();	
		Shark[][] temp = new Shark[r + 1][c + 1];
		while (!q.isEmpty()) {
			Shark shark = q.poll();
			for (int i = 0; i < shark.s; i++) {
				shark.r += dir[shark.d - 1][0];
				shark.c += dir[shark.d - 1][1];

				if (shark.r == 0) { //
					shark.r = 2;
					shark.d = 2;
				} else if (shark.r == r + 1) {
					shark.r = r - 1;
					shark.d = 1;
				}

				if (shark.c == 0) {
					shark.c = 2;
					shark.d = 3;
				} else if (shark.c == c + 1) {
					shark.c = c - 1;
					shark.d = 4;
				}
			}
			if (temp[shark.r][shark.c] == null || temp[shark.r][shark.c].z < shark.z)
				temp[shark.r][shark.c] = shark;
		}
		sharks = temp;
	}

	public static Shark findsharks(int col) {
		for (int i = 1; i <= r; i++) {
			if (sharks[i][col] != null) {
				return sharks[i][col];				
			}
		}
		return null;
	}

	static class Shark {
		int r, c, s, d, z; // r,c는 위치 s는 속력, d는 이동방향, z는 크기

		public 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;
		}
	}
}