[SW 역량테스트 기출풀이] 백준 - 17143 낚시왕

 문제 

[BOJ 17143 : 낚시왕]

17143번: 낚시왕

흔히 말하는 맞왜틀을 방지하기위해서 문제를 풀기전에 읽고 해설하는데  시간을 쏟는 연습을 하고 있습니다. 그럼에도 불구하고 원트라이에 풀지 못하였는데, 어디서 막혔었고, 어디서 시간이 많이 소비되었는지 확인하며 포스팅 하도록 해보겠습니다.

 

 조건 확인 

1. 상어들은 각 (r,c) (r : 행, c : 열)에 존재한다. 

 

2. 낚시왕은 처음에 1번 열의 한칸 왼쪽에 있다. 낚시왕이 가장 오른쪽 열의 오른쪽으로 이동하면 이동을 멈춘다.

 

3. 1초동안 일어나는 일.

• 낚시왕이 오른쪽으로 한 칸 이동한다.
• 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
• 상어가 이동한다.

 

4. 상어는 주어진 속도(칸/초)로 이동한다. 만약 경계선에 도달시 방향전환 후 이동한다.

 

5. 1초동안 상어의 모든 이동 후에 같은 칸에 있는 상어중에 크기가 가장 큰 상어만이 살아 남는다.

 

6. 낚시왕이 잡은 상어 크기의 합을 구해보자.

 

• 입력 : 격자판 : R, C(행,열),M(상어의 수) 상어 : r, c (행, 열) , s(속도), d(방향), z(사이즈)
• 출력 : 낚시왕이 잡은 상어 크기의 합

 

 해설 

조건에 따른 구현 방향을 설명하겠습니다. 

 

1. 스킵

 

2. 낚시왕이 가장 왼쪽인덱스의 왼쪽부터 가장 오른쪽인덱스의 오른쪽 까지 이동하는 것은 사실입니다. 그러나 우리가 구하고자 하는 것은 낚시왕이 잡은 상어크기의 합이기 때문에 상어를 언제잡을 수 있는지를 확인해야 합니다.  낚시왕과 같은 열에 있는 상어만 잡을 수 있으므로 결국 낚시왕이 격자판 위에 있을때만 고려하면됩니다.

 

3. 1초동안 일어나는 일은 순서대로 구현을 하면됩니다.

 

4. 상어의 이동은 주어진 속도를 이용해서 시물레이션을 해도 되겠으나 격자판의 크기와 속도의 크기를 비교해서 최적화 할 수 있습니다. 즉, *(현재 위치)와 (주어진 방향으로 이동해서 격자판의 끝 사이의 거리)의 관계로 연산을 통해 방향 전환 하기 전까지의 위치를 파악할 수 있습니다. 따라서 방향전환이 이루어진다면 *친 부분을 반복하고, 방향전환이 이루어지지 않는다면 반복을 탈출합니다.

 

5. 1초동안 이동 후에 같은 위치에 있는 상어들중 사이즈가 가장큰 것을 제외한 나머지를 처리하는 것이 이문제의 핵심입니다. 방법은 여러가지 이지만 자칫하면 TO가 날 수 있기 때문에, 알맞은 자료구조나 또는 알고리즘을 구상해야합니다.

 

저는 상어들이 이동한 맵을 새로 만들고 그 맵에서 상어들의 위치가 같을때 사이즈가 큰것으로 내림차순을 하는 방법을 이용했습니다.

 

이렇게 해도 충분히 통과 되었지만, 다른사람들의 코드를 본 결과 조금더 최적화하기 위해서 상어들이 이동한 맵을 새로 만들어주지 않고 상어들의 번호를 매긴 후 상어들의 움직임을 체크하는 맵을 만들어 주는 방법을 이용한것을 확인했습니다. 

 

6. 낚시왕이 잡은 상어사이즈의 합을 구하면됩니다.

 

 구현 

 

C++ (@author 기록강박증) 

#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define X first
#define Y second
#define push(a,r,c,s,d,z) a.push_back(pi5(pii(z, c), pi3(pii(s, d), r)))
using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, int> pi3;
typedef pair<pii, pi3> pi5;

// s : 속도 d : 1,2,3,4 (U,D,R,L) z : 크기
int R, C, M, r, c, s, d, z, cy, cx, sum = 0;
vector<pi5> m;
vector<pi5> nm;

bool thatValue(const pi5& p) { return (p.Y.Y == cy && p.X.Y == cx); }

void go(int y, int x, int speed, int dir, int size)
{
	int ny = y, nx = x, nd = dir, ns = speed;
	bool flag = true;
	/*
		한 방향으로 갈때 속도*시간(sec) 보다 남은 거리가 크다면 도착위치 지정 후 break
		작다면, 지나간 거리만큼 속도를 감소시키고 반복.
	*/
	while (flag)
	{
		switch (nd)
		{
		case 1:
			if (ny >= ns)
				ny -= ns, flag = false;
			else
				ns -= ny , ny = 0, nd = 2;
			break;
		case 2:
			if (R - 1 - ny >= ns)
				ny += ns, flag = false;
			else
				ns -= (R - 1 - ny), ny = R - 1, nd = 1;
			break;
		case 3:
			if (C - 1 - nx >= ns)
				nx += ns, flag = false;
			else
				ns -= (C - 1 - nx), nx = C - 1, nd = 4;
			break;
		case 4:
			if (nx >= ns) 
				nx -= ns, flag = false;
			else
				ns -= nx, nx = 0, nd = 3;
			break;
		}
	}
	// 다음 상어의 위치를 저장
	push(nm, ny, nx, speed, nd, size);
}

void Solution()
{
	for (int i = 0; i < C; ++i)
	{
		bool visited[101][101] = { 0, };

		// 낚시
		for (int j = 0; j < R; ++j)
		{
			cy = j, cx = i;
			vector<pi5>::iterator itr = find_if(all(m), thatValue);

			// 만약 같은 열에 데이터가 있다면 삭제후 break
			if (itr != m.end())
			{
				sum += (*itr).X.X;
				visited[j][i] = true;
				break;
			}
		}

		// base condition (열을 벗어날 경우)
		if (i == C - 1)
		{
			cout << sum;
			exit;
		}

		// 상어 이동
		for(const pi5& p : m)
		{
			int y = p.Y.Y;
			int x = p.X.Y;

			if (visited[y][x]) continue;
			visited[y][x] = true;

			int speed = p.Y.X.X;
			int dir = p.Y.X.Y;
			int size = p.X.X;

			// logic
			if (speed > 0)
				go(y, x, speed, dir, size);
			else
				push(nm, y, x, speed, d, size);
		}

		// 같은 위치 사이즈가 큰것부터 (내림차순 sort)
		sort(all(nm), greater<pi5>());
		// 상어의 위치를 갱신
		m = nm;
		nm.clear();
	}
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> R >> C >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> r >> c >> s >> d >> z;
		push(m,r - 1, c - 1, s, d, z);
	}

	Solution();
}

 

Java (@author 고수가 되고싶어요) 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int r, c, m;
	static int[] dx = { 0, -1, 1, 0, 0 };
	static int[] dy = { 0, 0, 0, 1, -1 };
	static int[] reverse = { 0, 2, 1, 4, 3 };

	static class Shark {
		int x, y, s, d, z;

		public Shark() {
			
		}

		public Shark(int x, int y, int s, int d, int z) {
			this.x = x;
			this.y = y;
			this.s = s;
			this.d = d;
			this.z = z;
		}

	}

	static int result;

	static void fishing(int pos) {
		for(int i = 1; i<=r; i++) {
			if(map[i][pos] != 0) {
				result += list[map[i][pos]].z;
				list[map[i][pos]] = null;
				map[i][pos] = 0;
				break;
			}
		}
	}

	// 좌표 : (x, y) , 속도 : s , 방향 : d, 크기 : z
	static void move() {
		map = new int[r+1][c+1];
		for (int i = 1; i < list.length; i++) {
			if(list[i] == null) continue;
			Shark sh = list[i];
			// 속도 만큼 이동
			// 벽에 박으면 상어는 방향을 전환한다.
			// 1 <-> 2 3 <-> 4
			int nx = sh.x, ny = sh.y;
			int loop = 0;
			int speed = sh.s;
			if(sh.d < 3) 
				loop = 2 * (r - 1);
			else
				loop = 2 * (c - 1);
			if(speed >= loop) speed %= loop;
			
			for (int j = 0; j < speed; j++) {
				nx += dx[sh.d];
				ny += dy[sh.d];
				// 닿으면 방향을 거꾸로 돌린다.
				if (nx < 1 || nx > r || ny < 1 || ny > c) {
					sh.d = reverse[sh.d];
					// 2번 이동해야 이전 상태에서 역으로 이동
					nx += 2 * dx[sh.d];
					ny += 2 * dy[sh.d];
				}
			}
			// 상어의 좌표 갱신
			sh.x = nx;
			sh.y = ny;
			
			
			if(map[sh.x][sh.y] != 0) {
				Shark temp = list[map[sh.x][sh.y]];
				if(temp.z > sh.z) {
					list[i] = null;
				}else {
					list[map[sh.x][sh.y]] = null;
					map[sh.x][sh.y] = i; 
				}
			}else {
				map[sh.x][sh.y] = i;
			}
		}// for
		
	}

	static Shark[] list;
	static int[][] map;
	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 = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		list = new Shark[m+1];
		map = new int[r+1][c+1];
		for (int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			list[i] = new Shark(x, y, s, d, z);
			map[x][y] = i;
		}
		for (int i = 1; i <= c; i++) {
			fishing(i);
			move();
		}
		System.out.println(result);
	}
}

 

 회고 

이 문제를 해결하는데 2시간 30분이 걸렸다. SW역량 테스트 A+를 취득하기 위해서는 1시간~1시간 30분에 문제를 해결해야 하는데, 어디서 시간이 오래 걸렸었는지 확인해보자. 또한 3번의 트라이만에 풀었었는데 틀렸었던 이유가 무엇인지 확인해보자.

 

시간을 잡아먹었던 이유 : 조건 3~4에서 1초동안 일어나는 일에서는 기존 맵에 있던 상어들만 해당하게 알고리즘을 구상해야하는데, 1초동안 움직인 상어를 같은 맵에 저장해두어서 디버깅하는데 시간이 걸렸다. 또한 STL find_if를 처음써봐서 혹시 이것에 문제가 있나 확인을 하는데 오래 걸렸다.

 

두번 틀렸었던 이유 : 문제를 잘 읽어 보겠다고 시간을 투자해서 읽었지만, 출력값이 낚시왕이 잡은 상어 사이즈의 합이라는 것을 착각했다. 또한 두번째 트라이에서 틀린이유는 TO가 났었는데, 상어의 움직임을 삽입/삭제 연산을 통해서 해결하려는 집착이 있었던것 같다. 그래서 결국 구현하였더니 TO가 났다. 삽입/삭제에 사용여부에 대해서 다시한번 생각해 볼 필요가 있다. 

 

기본적으로 삽입 삭제가 많으면 list를 쓰지만, 적다면 vector를 이용하는게 빠르다. 이유는 list가 삽입을 할때 O(n)의 복잡도를 가지기 때문이다. 

 

참조 : C++ benchmark – std::vector VS std::list VS std::deque | Blog blog("Baptiste Wicht");