글 읽기 - c++ 틀린점이나 반례좀 알려주셨으면합니다.(주석 있음)

dkxm99 3년 전 0

일단 예제는 전부 정답으로 뜹니다. 또 제가 따로 예제를 만들어서 넣어봤지만 전부 예상한 결과와 같은 답이 출력이 됐습니다.

제가 놓친부분이 있을까요?

코드 설명은 주석으로 해놨습니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#define MAX (50 + 1)

using namespace std;
int map[MAX][MAX];
int chicken;
bool visited[MAX][MAX];
int n, m, cntChicken, cntTemp;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

struct tempMap { //모든 치킨집의 좌표값과 해당 치킨집에서 모든 집간의 거리를 저장하는 함수
	int dist;
	int x;
	int y;
};

tempMap temp[15];

bool comp(const tempMap temp1, const tempMap temp2) { //치킨집에서 집들간의 총 거리가 작은순으로 정렬
        return temp1.dist < temp2.dist;
}

void bfsHouse(int b, int a) { //치킨집에서 집들간의 총 거리를 구하는 bfs
	queue<pair<pair<int, int>, int>>q;
	visited[b][a] = true;
	q.push(make_pair(make_pair(b, a), 0));
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second;
		q.pop();
		if (map[y][x] == 1) { //집을 찾을때마다 모든 치킨집의 위치와 거리 저장
			temp[cntChicken].y = b;
			temp[cntChicken].x = a;
			temp[cntChicken].dist += cnt;  //예제 1번 기준으로 소요거리는 7,7,17 순으로 저장됨
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (!visited[ny][nx]) {
				visited[ny][nx] = true;
				q.push(make_pair(make_pair(ny, nx), cnt + 1));
			}
		}
	}
}

void bfsChicken(int b, int a) { //집에서 치킨집간의 거리를 구하는 bfs
	queue<pair<pair<int, int>, int>>q;
	visited[b][a] = true;
	q.push(make_pair(make_pair(b, a), 0));
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second;
		q.pop();
		if (map[y][x] == 3) { //m개를 충족하는 치킨집을 찾았을때 
			chicken += cnt;  // 소요되는 모든거리를 합산함
			return;
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (!visited[ny][nx]) {
				visited[ny][nx] = true;
				q.push(make_pair(make_pair(ny, nx), cnt + 1));
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 2 && !visited[i][j]) {
				bfsHouse(i, j);
				cntChicken++;
				memset(visited, 0, sizeof(visited));
			}
		}
	}
	sort(temp, temp + cntChicken, comp); // 거리순으로 정렬
	for (int i = 0; i < m; i++) { // 거리순으로 정렬한것을 최대 m개의 치킨집까지 맵에다가 3으로 저장 
		map[temp[i].y][temp[i].x] = 3; //예제 1번기준으로는 3개 전부 저장, 2번기준으로는 2개까지 저장
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				bfsChicken(i, j); //위에서 정렬한 치킨집을 탐색함. 
				memset(visited, 0, sizeof(visited));
			}
		}
	}
	cout << chicken; //결과 출력
	return 0;
}

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

문제

문제

출처

ICPC

c++ 틀린점이나 반례좀 알려주셨으면합니다.(주석 있음)

dkxm99 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말