[SWEA] 5644 무선충전

1. 문제

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE

SW Expert Academy

2. 접근방법

시뮬레이션 문제이다.

 

먼저 BC의 정보들을 나타내기 위해

1 . 각 BC에 번호를 지정해 배열하나에 충전세기를 저장해두고

 

2. List형태의 map을 만들어

 

3. BC의 위치부터 범위만큼 bfs를 돌리며 값들을 해당 좌표의 List에 저장했다.

 

그 다음 A와 B를 이동 시키는데

각각 이동 시킨 위치에서 신호의 최댓값을 가진 BC의 번호를 찾는다

 

이후 A와 B가 같은 BC의 값을 가지고 있다면

1) A와 B 둘 다 2개 이상의 신호를 받을 수 있는 경우

이 땐 처음 찾은 BC를 제외한

다른 A위치의 최댓값과

다른 B위치의 최댓값 

2개를 비교해 더 큰 값을 가진 얘의 값만 새로 찾은 BC로 바꿔준다.

 

2) A나 B 둘중 한명만 2개이상의 신호를 받는 경우

무조건 2개 이상을 받는 친구가

처음 찾은 BC를 제외한

다른 최댓값을 찾아 바꾼다.

 

3) 둘 다 최초 찾은 BC만 신호를 받는 경우

이 경우 A와 B가 반반 받으니

총 받는 값은 1명이 다 받는것과 같아지므로

 

그냥 B의 값을 0으로 설정했다.

 

------

이 방식으로 M번 만큼 시뮬을 돌리면 정답이 나오게 된다.

 

3. 자바 코드

package D4;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class P5644무선충전 {

	static List<Integer> map[][];
	static int bcinfo[];
	static int moveA[], moveB[], M;
	static Point A, B;
	static int score;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken()); // time
			int Ap = Integer.parseInt(st.nextToken()); // Ap cnt
			map = new List[10][10];
			bcinfo = new int[Ap + 1];
			score = 0;
			moveA = new int[M];
			moveB = new int[M];
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			for (int i = 0; i < M; i++) {
				moveA[i] = Integer.parseInt(st1.nextToken()) - 1;
				moveB[i] = Integer.parseInt(st2.nextToken()) - 1;
			}
			for (int i = 1; i <= Ap; i++) {
				st = new StringTokenizer(br.readLine());
				int y = Integer.parseInt(st.nextToken()) - 1;
				int x = Integer.parseInt(st.nextToken()) - 1;
				int c = Integer.parseInt(st.nextToken());
				int p = Integer.parseInt(st.nextToken());
				bcinfo[i] = p;
				spread(x, y, c, i);
			}
			A = new Point(0, 0);
			B = new Point(9, 9);
			go();
			System.out.println("#" + tc + " " + score);
		}

	}

	static int dr[] = { -1, 0, 1, 0 };
	static int dc[] = { 0, 1, 0, -1 };

	static void go() { // 점수 올리고 이동하고
		for (int i = 0; i <= M; i++) {
			List<Integer> Anum = map[A.x][A.y];
			List<Integer> Bnum = map[B.x][B.y];
			int sumA = findMax(Anum, -1);
			int sumB = findMax(Bnum, -1);
			if (sumA != 0 && sumA == sumB) {
				if (Anum.size() > 1 && Bnum.size() > 1) {
					int a = findMax(Anum, sumA);
					int b = findMax(Bnum, sumB);
					if (bcinfo[a] > bcinfo[b])
						sumA = a;
					else
						sumB = b;
				} else if (Anum.size() > 1) {
					sumA = findMax(Anum, sumA);
				} else if (Bnum.size() > 1) {
					sumB = findMax(Bnum, sumB);
				} else {
					sumA = sumA;
					sumB = 0;
				}
			}
			score += bcinfo[sumA];
			score += bcinfo[sumB];
			if (i == M)
				break;
			if (moveA[i] != -1) {
				A = new Point(A.x + dr[moveA[i]], A.y + dc[moveA[i]]);
			}
			if (moveB[i] != -1) {
				B = new Point(B.x + dr[moveB[i]], B.y + dc[moveB[i]]);
			}
		}
	}

	static int findMax(List<Integer> nums, int ex) {
		int max = 0;
		if (nums != null) {
			for (int i : nums) {
				if (i != ex && bcinfo[max] < bcinfo[i])
					max = i;
			}
		}
		return max;
	}

	static void spread(int x, int y, int c, int num) { // 맵 만들기
		Queue<Point> que = new LinkedList<Point>();
		boolean visited[][] = new boolean[10][10];
		visited[x][y] = true;
		que.offer(new Point(x, y));
		int dist = 0;
		while (!que.isEmpty()) {
			int size = que.size();
			for (int i = 0; i < size; i++) {
				Point now = que.poll();
				if (map[now.x][now.y] == null) {
					map[now.x][now.y] = new ArrayList<Integer>();
				}
				map[now.x][now.y].add(num);

				for (int d = 0; d < 4; d++) {
					int row = now.x + dr[d];
					int col = now.y + dc[d];
					if (row < 0 || col < 0 || row >= 10 || col >= 10)
						continue;
					if (visited[row][col])
						continue;
					visited[row][col] = true;
					que.offer(new Point(row, col));
				}
			}
			if (dist == c) {
				break;
			}
			dist++;
		}
	}

}

4. 마치며

그렇게 어려운 부분은 없었는데 조금 신선하게 느껴지긴 한 문제였다.