글 읽기 - 제발 도와주세요.. 두 코드의 차이를 모르겠습니다

sihyun93 4년 전 0

풀이 방식은 조합을 통해 m개를 고른 뒤에 bfs로 map을 탐색하며 최소값을 계속 갱신해 주는 식으로 진행하였습니다.

다만 제가 질문드리고 싶은건 if문을 쓰는 두가지 코드의 차이인데요...

첫번째는 주석 처리된 33~41번째 줄이 원래 코드입니다. (계속 오답을 받은 코드입니다.)

2. 두번째는43~50번째 줄처럼 if문을 반대로 바꾼뒤 그 조건일때에만 진행힌 코드입니다. (통과한 코드입니다.)

두 코드가 무슨 차이가 있는지 도저히 모르겠습니다.

질문의 요지를 정리하면,

34~41 번의 코드를 실행하는 것과, 43번 ~50번 코드를 실행하는 것이 어떠한 차이가 있는 것인가요?

답변 기다리고 있겠습니다. 읽어주셔서 감사합니다.

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define MAX 987654321
using namespace std;
typedef pair<int, int> p;
vector<p> virus;
vector<p> candidate;
queue<p> q;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int visited[50][50];
int map[50][50];
int n, m, vsize, csize;
int ans = MAX;
int spread;


void bfs() {
	int infection = 0; // 얘는 감염된 칸
	int time = 0; // 시간

	while (!q.empty()) {
		p cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            
            /* 원래 코드 */
	//		if (map[nx][ny] == 1 || visited[nx][ny] != -1) continue;
    //      visited[nx][ny] = visited[cur.first][cur.second] + 1;
	//	    q.push(make_pair(nx, ny));
	//		if (map[nx][ny] == 0) { // 바이러스 퍼뜨린거면
	//			infection++; // 감염++
	//			time = visited[nx][ny];
	//		}
            /* 원래코드 끝 */
            
			if (map[nx][ny] != 1 && visited[nx][ny] == -1) {
				visited[nx][ny] = visited[cur.first][cur.second] + 1;
				q.push(make_pair(nx, ny));
				if (map[nx][ny] == 0) { // 바이러스 퍼뜨린거면
					infection++; // 감염++
					time = visited[nx][ny];
				}
			}
		}
	}
	if (infection == spread && ans > time) ans = time; // 다 채운 경우에만 ans update
	return;
}
void select(int idx) { // permutation 함수
	csize = candidate.size();
	if (csize == m) { // m개 골랐으면 bfs 시작
		memset(visited, -1, sizeof(visited)); // visited 다 -1초로 초기화
		for (int i = 0; i < csize; i++) {
			q.push(candidate[i]); // 후보자들 다 넣고 시작
			visited[candidate[i].first][candidate[i].second] = 0; // 시작점들만 0초로 초기화
		}
		bfs();
		return;
	}
	if (idx >= vsize) return;

	int x = virus[idx].first;
	int y = virus[idx].second;

	candidate.push_back(make_pair(x, y));
	select(idx + 1);
	candidate.pop_back();
	select(idx + 1);
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 0) spread++; // spread는 퍼져야할 칸 수
			else if (map[i][j] == 2) virus.push_back(make_pair(i, j));
		}
	}

	vsize = virus.size();
	select(0);
	ans == MAX ? printf("-1\n") : printf("%d\n", ans);
	return 0;
}

chocodog 4년 전 1

저는 첫번째와 두번째 모두 정답으로 나오는데 뭔가 착오가 있었던 것 같습니다.

아래 코드는 정답으로 나온 주석 처리 안한 원래 코드입니다.

감사합니다.

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#define MAX 987654321
using namespace std;
typedef pair<int, int> p;
vector<p> virus;
vector<p> candidate;
queue<p> q;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int visited[50][50];
int map[50][50];
int n, m, vsize, csize;
int ans = MAX;
int spread;


void bfs() {
	int infection = 0; // 얘는 감염된 칸
	int time = 0; // 시간

	while (!q.empty()) {
		p cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            
            /* 원래 코드 */
			if (map[nx][ny] == 1 || visited[nx][ny] != -1) continue;
            visited[nx][ny] = visited[cur.first][cur.second] + 1;
		    q.push(make_pair(nx, ny));
			if (map[nx][ny] == 0) { // 바이러스 퍼뜨린거면
				infection++; // 감염++
				time = visited[nx][ny];
			}
            /* 원래코드 끝 */
       
		}
	}
	if (infection == spread && ans > time) ans = time; // 다 채운 경우에만 ans update
	return;
}
void select(int idx) { // permutation 함수
	csize = candidate.size();
	if (csize == m) { // m개 골랐으면 bfs 시작
		memset(visited, -1, sizeof(visited)); // visited 다 -1초로 초기화
		for (int i = 0; i < csize; i++) {
			q.push(candidate[i]); // 후보자들 다 넣고 시작
			visited[candidate[i].first][candidate[i].second] = 0; // 시작점들만 0초로 초기화
		}
		bfs();
		return;
	}
	if (idx >= vsize) return;

	int x = virus[idx].first;
	int y = virus[idx].second;

	candidate.push_back(make_pair(x, y));
	select(idx + 1);
	candidate.pop_back();
	select(idx + 1);
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 0) spread++; // spread는 퍼져야할 칸 수
			else if (map[i][j] == 2) virus.push_back(make_pair(i, j));
		}
	}

	vsize = virus.size();
	select(0);
	ans == MAX ? printf("-1\n") : printf("%d\n", ans);
	return 0;
}

sihyun93 4년 전 0

착오가 있었네요...대단히 죄송합니다!

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

문제

문제

출처

ICPC

제발 도와주세요.. 두 코드의 차이를 모르겠습니다

sihyun93 4년 전 0

chocodog 4년 전 1

sihyun93 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말