글 읽기 - 21608문제 질문 드립니다.

kimbob122 2년 전 0

예시와 질문 게시판에 있는 반례들로 테스트 해봤을때 정답을 잘 출력하는데 제출시에는 바로 오답이 처리가 됩니다.

빈자리 기준으로 4방향으로 자기가 원하는 친구가 있는지 또는 빈칸인지를 검사하고 벡터에 넣고 조건에 맞게 정렬 후에 가장 처음 원소의 위치로 자리를 배정하는 방식을 했습니다.

혹시 어떤 부분을 놓쳤는지 지적 해주시면 정말 감사하겠습니다..

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 21;

int N;

vector<int> v[MAX * MAX];
int arr[MAX][MAX] = {};

struct sPos
{
	int r;
	int c;
}Delta[] = {
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1}
};

struct sSeatInfo
{
	int r;
	int c;
	int favCnt;
	int emptyCnt;

	sSeatInfo(int _r, int _c, int _favCnt, int _emptyCnt) :
		r(_r), c(_c), favCnt(_favCnt), emptyCnt(_emptyCnt)
	{}

};

int main()
{
	cin >> N;

	for (int i = 0; i < N * N; i++)
	{
		int num;

		// 학생 번호 입력
		cin >> num;
			
		// 좋아하는 학생 번호 입력 후 벡터에 기록
		for (int j = 0; j < 4; j++)
		{
			int favorite;

			cin >> favorite;

			v[num].push_back(favorite);
		}


		vector<sSeatInfo> temp;

		// 모든 자리를 검사
		for (int r = 0; r < N; r++)
		{
			for (int c = 0; c < N; c++)
			{
				int favCnt = 0;
				int emptyCnt = 0;

				// 만약 빈자리라면
				if (arr[r][c] == 0)
				{
					for (int k = 0; k < 4; k++)
					{
						int nr = r + Delta[k].r;
						int nc = c + Delta[k].c;

						if (nr < 0 || nc < 0 || nr >= N || nc >= N)
							continue;
						
						// 만약 주변에 학생이 앉아있다면
						if (arr[nr][nc] != 0)
						{
							// 좋아하는 학생목록에 포함되어있는지를 찾는다.
							auto iter = find_if(v[num].begin(), v[num].end(), [&](const int a) {
								return a == arr[nr][nc];
							});

							// 만약 존재한다면 카운트를 늘려준다.
							if (iter != v[num].end())
							{
								favCnt++;
							}
						}
						// 빈자리일 경우
						else
							emptyCnt++;

					}

					temp.push_back(sSeatInfo(r, c, favCnt, emptyCnt));

				}
			}
		}

		// 문제에 나온 조건대로 정렬을 한다.
		sort(temp.begin(), temp.end(), [](const sSeatInfo& a, const sSeatInfo& b) {
			if (a.favCnt != b.favCnt)
				return a.favCnt > b.favCnt;
			else if (a.favCnt == b.favCnt)
				return a.emptyCnt > b.emptyCnt;
			else
			{
				if (a.r != b.r)
					return a.r < b.r;
				else
					return a.c < b.c;
			}
		});

		// 가장 처음에 위치한 원소의 값으로 자리를 배정
		arr[temp[0].r][temp[0].c] = num;
	}

	int ans = 0;


	// 만족도 계산
	for (int i = 0; i < N; i++)
	{

		for (int j = 0; j < N; j++)
		{
			int cnt = 0;

			for (int k = 0; k < 4; k++)
			{
				int nr = i + Delta[k].r;
				int nc = j + Delta[k].c;

				if (nr < 0 || nc < 0 || nr >= N || nc >= N)
					continue;

				auto iter = find_if(v[arr[i][j]].begin(), v[arr[i][j]].end(), [&](const int a) {
					return a == arr[nr][nc];
				});

				if (iter != v[arr[i][j]].end())
					cnt++;
			}

			switch (cnt)
			{
			case 0:
				break;
			case 1:
				ans += 1;
				break;
			case 2:
				ans += 10;
				break;
			case 3:
				ans += 100;
				break;
			case 4:
				ans += 1000;
				break;
			}
		}
	}


	cout << ans << "\n";

	return 0;
}

qkfskan82 2년 전 1

sorting 람다식의 두번째 조건문이 else if (a.favCnt == b.favCnt)가 아니라 else if (a.emptyCnt != b.emptyCnt) 아닐까요?

지금 코드에서는 두번째 조건문에서 모든 케이스가 처리돼서 세번째 조건,

3. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

이 친구가 동작안할것 같습니다.

kimbob122 2년 전 0

qkfskan82님 감사합니다. 말씀하신대로 두번째 조건이 이상했던거였네요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

21608문제 질문 드립니다.

kimbob122 2년 전 0

qkfskan82 2년 전 1

kimbob122 2년 전 0

qkfskan82님 감사합니다. 말씀하신대로 두번째 조건이 이상했던거였네요..

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말