글 읽기 - 0%에서 틀렸습니다가 나옵니다... 로직 확인해주시면 감사하겠습니다...

supergrammer 3년 전 0

S전자 문제 복기를 하기 위해 문제를 풀었습니다.

그런 이유로 파이어볼이 아닌 Planets 로 변수명을 설정하였습니다.

기본적인 아이디어는 Map 을 N * N 배열 각각의 원소를 리스트로 구현하여 파이어볼의 위치를 표시하고, 이의 정보를 Planets 라는 리스트에서 가지고 있게끔 하는 방식입니다.

move() 에서는 리스트의 파이어볼을 모두 검사해 이동시키고, 맵 상에서 이동시킵니다.

그 아래의 collide() 는 Map[i][j] 의 크기가 2 이상이 되면 충돌이 일어나게 되고, 이를 처리하는 함수입니다. d가 홀수라면 Odd = True, 짝수라면 Even = True 상태가 되고, 아래에서 Odd and Even 을 검사하여 파이어볼이 퍼져나가는 방향을 결정하게 됩니다.

이 방식이 제가 역량테스트에서 문제를 풀었던 방식입니다.

그런데 3일째 문제를 푸는데도 0% 에서 틀렸습니다가 출력되는데 혹시 제가 놓치는 부분이 있을까요??

물론 역량테스트를 풀 당시에는 10개 TC 모두 통과했습니다.

고수님들의 조언 부탁드립니다.

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
Map = [[[] for _ in range(N)] for _ in range(N)]
planets = []
dir = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]
answer = 0

for i in range(M):
    y, x, m, s, d = map(int, input().split())
    Map[y - 1][x - 1].append(i)
    planets.append([y - 1, x - 1, m, s % N, d])

# 충돌처리 함수, len(Map[i][j]) 일때 실행함
def collide(arr):
    y, x = planets[arr[0]][:2]
    tm, ts = 0, 0
    Odd, Even = False, False
    divided = []

    for planet in arr:
        m, s, d = planets[planet][2:]
        if d % 2 == 0: Even = True
        else: Odd = True
        tm += m; ts += s
        planets[planet] = []

    tm //= 5; ts //= len(arr)
    if tm == 0:
        return divided

    if Odd and Even:
        for i in [1, 3, 5, 7]:
            divided.append([y, x, tm, ts, i])
    else:
        for i in [0, 2, 4, 6]:
            divided.append([y, x, tm, ts, i])

    return divided

# 파이어볼의 이동 및 맵 갱신
def move():
    cpyMap = [[[] for _ in range(N)] for _ in range(N)]
    for i in range(len(planets)):
        if planets[i]:
            y, x, m, s, d = planets[i]
            y = (y + dir[d][0] * s + N) % N
            x = (x + dir[d][1] * s + N) % N
            planets[i] = [y, x, m, s, d]
            cpyMap[y][x].append(i)

    for i in range(N):
        for j in range(N):
            if len(cpyMap[i][j]) >= 2:
                divided = collide(cpyMap[i][j])
                cpyMap[i][j] = []
                for planet in divided:
                    planets.append(planet)
                    cpyMap[i][j].append(len(planets) - 1)

    return cpyMap

for _ in range(K):
    Map = move()
for planet in planets:
    if planet:
        answer += planet[2]

print(answer)

danimartinwife 3년 전 0

저도 인터넷에 정답이라고 올리신 분 코드랑 비교해보니 전체적인 로직은 같았습니다. 그래서 대각선일때 잘못 처리했나 싶어서 댓글 달았는데 질문주신분께서 맞게 본거라고 말씀하셨구요. 불필요한 속도 게산 반복문은 나머지연산자로 처리했습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
#define SIZE 50
typedef pair<int, int> pii;
int N, M, K;
int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int pos[SIZE + 10][SIZE + 10];

bool inRange(int r, int c) {
	return r >= 0 && c >= 0 && r < N && c < N;
}

struct Info {
	int r, c, w, dir, v;
	Info(int r, int c, int w, int dir, int v) {
		this->r = r;
		this->c = c;
		this->w = w;
		this->dir = dir;
		this->v = v;
	}
	Info() {}
};

vector<Info> MAP[SIZE + 10][SIZE + 10];

void print() {
	printf("map status\n");
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (MAP[i][j].size()) printf("%d ", (int)(MAP[i][j].size()));
			else printf("0 ");
		}
		printf("\n");
	}
}

void solve(queue<Info> &q) {

	for (int turn = 0; turn < K; turn++) {
		//move
		while (!q.empty()) {
			int qsize = q.size();
			while (qsize--) {
				int r = q.front().r, c = q.front().c, dir = q.front().dir, velo = q.front().v, weight = q.front().w;
				q.pop();

				int nR = (r + dr[dir] * velo) % N, nC = (c + dc[dir] * velo) % N;

				if (nR < 0) {
					nR += N;
				}
				if (nC < 0) {
					nC += N;
				}

				MAP[nR][nC].push_back(Info(nR, nC, weight, dir, velo));
			}

		}


		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (MAP[i][j].empty()) continue;

				if (MAP[i][j].size() == 1) {
					q.push(MAP[i][j][0]);
				}
				else { //divide
					int weightSum = 0, veloSum = 0, dirSum = 0;

					for (auto &b : MAP[i][j]) {
						weightSum += b.w;
						veloSum += b.v;
						dirSum += b.dir;
					}

					int cnt = MAP[i][j].size();
					int weight = weightSum / 5;
					int velocity = veloSum / cnt;

					if (weight) {
						for (int k = 0; k < 4; k++) {
							int nd = (dirSum % 2) + k * 2;
							q.push(Info(i, j, weight, nd, velocity));
						}
					}

				}

				MAP[i][j].clear();
			}
		}

	}

	int ans = 0;

	while (!q.empty()) {
		ans += q.front().w; q.pop();
	}

	cout << ans << '\n';
}

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> N >> M >> K;

	queue<Info> balls;

	for (int i = 1; i <= M; i++) {
		int r, c, m, d, s;
		cin >> r >> c >> m >> s >> d; r -= 1, c -= 1;
		balls.push(Info(r, c, m, d, s));
	}

	//print();
	solve(balls);

	return 0;
}