글 읽기 - 안녕하세요 고수님들! 한번만 보고 가주시면 감사하겠습니다 ㅠㅠ

gamma0190 2년 전 0

고수님들의 절실한 가르침이 필요해서 이렇게 글을 올려봅니다!! 제시된 TC는 다 맞구요.. 게시판에 예외도 맞다고 나오는데 도대체 어디서 틀린건지 찾지를 못하겠습니다...ㅠㅠ 도와주신다면 너무 감사드리겠습니다!

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N = 0, M = 0;
int cnt = 0, sum = 0, result = 99;
int box[50][50] = { 0 };
int map[50][50] = { 0 };
int visited[50][50] = { 0 };

void Cal(int x, int y){
	vector <int> v;
	int temp = 99;

	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			if (map[i][j] == 2){
				v.push_back(abs((x - i)) + abs((y - j)));
			}
		}
	}
	for (int i = 0; i < v.size(); i++){
		temp = min(temp, v[i]);
	}

	sum += temp;
	//printf("%d\n", sum);
}

void DFS(int x, int y, int cnt){
	visited[x][y] = 1;

	if (cnt <= M - 1){
		// 지도 복사
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				map[i][j] = box[i][j];
			}
		}
		// M만큼 선택한 치킨 집 이외에는 폐업
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				if (visited[i][j] == 0 && map[i][j] == 2){
					map[i][j] = 0;
				}
			}
		}
		/*printf("\n");
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				printf("%d ", map[i][j]);
			}
			printf("\n");
		}*/
		// 거리 구하기
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				if (map[i][j] == 1){
					Cal(i, j);
				}
			}
		}
		result = min(result, sum);
		sum = 0;
	}
	if(cnt <  M-1){
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				if (visited[i][j] == 0 && box[i][j] == 2){
					DFS(i, j, cnt + 1);
				}
			}
		}
		return;
	}

}

int main(void){
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			scanf("%1d", &box[i][j]);
		}
	}

	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			if (box[i][j] == 2){
				DFS(i, j, cnt);
				visited[i][j] = 0;
			}
		}
	}

	printf("%d\n", result);
	return 0;
}

rhs0266 2년 전 1

visited[x][y]=1 을 한 이유는 x,y 에 있는 치킨집을 선택했다는 표시를 하기 위해서입니다.

그렇다면 재귀함수 DFS()가 끝나고 돌아갈 때에는 선택을 취소해야하기 때문에 visited[x][y]=0 을 수행하고 return 시켜야 합니다.

jh05013 2년 전 1

랜덤으로 만든 반례 드립니다.

2
1 0 2 0
0 0 0 0
0 0 1 0
0 1 1 0
1 1 2 2
Correct: 13
WRONG: 11

2
1 2 0 2
1 1 2 2
0 2 1 0
0 1 1 0
1 0 2 1
Correct: 14
WRONG: 10

2
0 0 1 0
0 0 2 2
0 2 0 1
0 1 0 2
2 1 2 0
Correct: 11
WRONG: 6

2
0 1 2 1 0
0 0 0 1 0
1 0 0 2 2
2 0 0 2 1
0 0 1 0 2
0 0 0 0 0
Correct: 15
WRONG: 9

3
0 2 1
0 1 0
2 0 1
1 0 2
Correct: 8
WRONG: 7

3
2 1 0 2
1 1 0 1
0 1 1 0
0 0 1 2
2 1 0 0
Correct: 15
WRONG: 14

Test completed in 16.27160954475403 seconds

gamma0190 2년 전 0

아이고 제가 중요한 부분을 놓치고 있었네요 ㅠㅠ 두분 다 너무 감사드립니다!!

jkjan 1년 전 0

이게 대체 어떻게 하면 15가 나오죠...???? 반례를 찾았는데도 왜 틀렸는지 모르겠네요

jh05013 1년 전 0

이렇게 치킨집을 남겨 두면 됩니다.

_ 0 1 2 1 0
_ 0 0 0 1 0
1 1 0 0 _ _
1 2 0 0 _ 1
0 0 0 1 0 _
0 0 0 0 0 0

jkjan 1년 전 0

하하 답글이 달릴 줄은 몰랐네요... 최단 거리를 찾는데서 잠깐 잘못 생각한게 있어서 못찾은 거였습ㄴ다. 감사합니다.

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

문제

문제

출처

ICPC

안녕하세요 고수님들! 한번만 보고 가주시면 감사하겠습니다 ㅠㅠ

gamma0190 2년 전 0

rhs0266 2년 전 1

jh05013 2년 전 1

gamma0190 2년 전 0

jkjan 1년 전 0

jh05013 1년 전 0

jkjan 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말