Dazzling 개발 노트

[백준] 17143 - 낚시왕 (Java) 본문

Algorithm/백준

[백준] 17143 - 낚시왕 (Java)

dj._.dazzling 2023. 7. 26. 11:40

[백준] 17143 - 낚시왕 (Java)

문제

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

풀이/후기

문제를 읽을 때는 좀 혼란스러웠지만

풀어보니 생각보다 엄청 어렵지는 않았다.

처음 입력을 받을 때 데이터를 어떤식으로 가지고 있을까 고민이 많았는데

sharkinfo라는 1차원 배열을 이용해 0에는 속력, 1에는 이동방향, 2에는 크기 이런식으로 생각하여 저장했다.

(사실 이런 문제 나오면 입력 어떻게 받을지부터 한참을 고민하던 나였는데... 이렇게 바로 생각해낼 수 있어서 얼마나 뿌듯한지...!ㅎ)

그다음엔 문제에서 나온대로 차근차근 코드를 짰다.

어부가 map의 가장 오른쪽까지 이동하면 종료되고

이동할 때 가장 가까운 열의 상어를 잡은 후 상어가 이동하는 함수를 호출해주면 된다.

사실 메인은 이 상어 이동 함수였는데, 그냥 항상 그래프 문제 풀듯이 상하 또는 좌우로 이동하다 범위 밖 수치가 나오면 방향을 180도 변경해서 다시 탐색하면 된다. 이때 칸을 이동하는 횟수 관리를 잘 해야하는데, 난 이런 경우 i--를 해서 범위 밖 수치가 나온 경우는 이동하지 않은 것처럼 처리를 했다.(이것도 바로 생각하고 고려한 것에 뿌듯!)

 

디버깅 계속 돌려가면서 제대로 들어가는지 확인하고

어떤 경우에 잘못들어가는지 확인해서 하나씩 고치고,, 

그러다 보니 완성이 되었다. 사실 이렇게 풀어놓고 오답 나오거나 시간초과 나오면 그때부터 멘탈 바사삭인데

이번엔 바로 통과를 하니 기분이 너무 좋았다...ㅜㅜ

검색 한 번 없이 골드1 구현 문제를 바로 풀어내다니!!!

그치만 효율 비교하면 시간이 오래 걸리는 코드라 수정이 필요함.

(언제할거야 그래서?) 일단 자소서 좀 쓰고... 그때까진 이 승리의 기분을 느끼게 해줘..ㅎ

코드

package Samsung;

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

public class Problem17143 {

	static int R, C, M;
	static int result = 0; // 잡은 상어의 크기의 합
	static int[][] sharkInfo;
	static int[][] map;
	static int[][] temp;
	static int[][] dir = { { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } }; // 상 하 우 좌

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine());

		R = Integer.parseInt(str.nextToken()); // 행
		C = Integer.parseInt(str.nextToken()); // 열
		M = Integer.parseInt(str.nextToken());

		sharkInfo = new int[M + 1][3];
		map = new int[R + 1][C + 1];

		for (int i = 1; i < M + 1; i++) {
			str = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(str.nextToken());
			int y = Integer.parseInt(str.nextToken());
			// i = 상어의 번호
			map[x][y] = i;

			for (int j = 0; j < 3; j++) {
				// 0 = s(속력)
				// 1 = d(이동 방향)
				// 2 = z(크기)
				sharkInfo[i][j] = Integer.parseInt(str.nextToken());
			}
		}

		int T = 0; // 어부의 위치
		while (T++ < C) {
			// 어부의 위치에 상어가 있는지 확인
			for (int i = 1; i <= R; i++) {
				if (map[i][T] != 0) {
					// 어부의 위치에 상어가 있는 경우
					int sharkNum = map[i][T];
					// 상어를 잡음
					map[i][T] = 0;
					// 잡은 상어의 크기를 더함
					result += sharkInfo[sharkNum][2];
					// 땅과 가장 가까운 상어를 잡으므로 다음 반복문 미진행
					i = R + 99;
				}

			}

			temp = new int[R + 1][C + 1];
			// 상어의 이동
			sharkFunc();
			// 새로 변경된 temp배열을 map에 밀어넣기
			for (int i = 1; i <= R; i++) {
				for (int j = 1; j <= C; j++) {
					map[i][j] = temp[i][j];
				}
			}
		}
		
		System.out.println(result);

	}

	// 상어의 이동
	static void sharkFunc() {
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				if (map[i][j] != 0) {
					/**
					 * A B C D E F G H
					 * 1 2 3 4 5 6 7 8
					 */
					int sharkNum = map[i][j];
					int s = sharkInfo[sharkNum][0]; // 상어의 속도
					int d = sharkInfo[sharkNum][1]; // 상어의 방향

					moovingFunc(sharkNum, s, d, i, j);
				}
			}
		}
	}

	static void moovingFunc(int sn, int s, int d, int x, int y) {

		int nx = 0, ny = 0;
		if (s == 0) {
			nx = x; ny = y;
		} else {
			for (int i = 0; i < s; i++) {
				nx = x + dir[d][0];
				ny = y + dir[d][1];

				if (nx < 1 || ny < 1 || nx > R || ny > C) {
					if (d == 1)
						d = 2;
					else if (d == 2)
						d = 1;
					else if (d == 3)
						d = 4;
					else if (d == 4)
						d = 3;
					i--;
				} else {
					x = nx;
					y = ny;
				}
			}
		}
		
		sharkInfo[sn][1] = d;

		// 같은 칸에 상어가 두마리면 큰 상어만 남음
		if (temp[nx][ny] != 0 ) {
			int tn = temp[nx][ny];
			if (sharkInfo[tn][2] > sharkInfo[sn][2]) {
				//원래 있던 상어가 더 큰 경우
				temp[nx][ny] = temp[nx][ny];
			} else {
				//새로 온 상어가 더 큰 경우
				temp[nx][ny] = sn;
			}
		} else {
			temp[nx][ny] = sn;
		}
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/63d51b924769ffdf375c3edbfc8a3b6d96ebead2

참고