글 읽기 - 2606번: 큐에서 꺼낸 다음에 방문 표시하는 방식이 문제?

smahn9123 2년 전 0

큐에서 꺼낸 다음에 방문 표시하는 방식으로 하다가

큐에 넣기 전에 방문 표시하는 방식으로 바꿨더니 맞았습니다.

밑에 코드는 꺼낸 다음에 표시하는 방식인데,,

이러면 각 노드를 중복 방문은 하지만 그렇다고 왜 답이 틀리는지 모르겠습니다 ㅠㅠ

반례라도 있을까요?

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

#define SIZE 101
#define INFECTED 1

int m[SIZE][SIZE];
int com[SIZE];

int Q[SIZE*SIZE];
int rp, wp;

int empty()
{
	if (rp == wp)
		return 1;
	return 0;
}

int deq()
{
	if (empty())
		return -1;

	return Q[rp++];
}

int enq(int X)
{
	if (wp >= SIZE)
		return -1;
	Q[wp++] = X;
}

int main(void)
{
	int N, con, i, j, k, pc, infect_count;

//	freopen("input.txt", "r", stdin);

	scanf("%d%d", &N, &con);

	for (k = 0; k < con; k++)
	{
		scanf("%d %d", &i, &j);
		m[i][j] = m[j][i] = 1;
	}

	enq(1);
	infect_count = 0;
	while (!empty())
	{
		pc = deq();

		if (com[pc] != INFECTED)
		{
			com[pc] = INFECTED;

			for (i = 1; i <= SIZE - 1; i++)
			{
				if (m[pc][i] == 1 && com[i] != INFECTED)
					enq(i);
			}

			infect_count++;
		}
	}

	printf("%d\n", infect_count - 1);

	return 0;
}

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

문제

문제

출처

ICPC

2606번: 큐에서 꺼낸 다음에 방문 표시하는 방식이 문제?

smahn9123 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말