글 읽기 - 아.. 도와주십시오;;

whdnjqls456 6년 전 0

DFS 커트 조건 써서 시간초과를 넘겼는데,

50%에서 못 넘기겠습니다;;

이미 올라온 질문들에 적힌 반례들도 다 통과하는데 왜 안되는지 도저히 모르겠습니다 ㅜㅜ;;

도와주십시오 ㅜ_ㅜ...;

#include <stdio.h>
int arr[101][101];
int visit[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int N;
int count = 1;
int min = 200*200;

// 대륙 넘버링.
void DFS(int x, int y, int c)
{
// 대륙을 c라는 숫자로 넘버링 하는 DFS.
	arr[x][y] = c;

	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 (arr[nx][ny] == 1)
			DFS(nx, ny, c);
	}

	return;
}

// 최단거리를 찾는 DFS.
void Find(int x, int y, int c, int m)
{
    // 만약 현재 m이 최솟 값보다 크거나 같다면
    // 더이상 찾을 필요가 없기 때문에 커트
	if (m >= min)
		return;

    // 처음 DFS시작한 섬이 아니고,
    // 0도 아니라면 다른 대륙이기 때문에
    // 최솟 값 비교.
	if (arr[x][y] != c && arr[x][y] != 0)
	{
		if (min > m-1)
			min = m-1;
		return;
	}

    // 커트 조건을 위한 visit.
	visit[x][y] = 1;

	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 (arr[nx][ny] != c && visit[nx][ny] == 0)
			Find(nx, ny, c, m + 1);
	}

	return;
}

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

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			scanf("%d", &arr[i][j]);
	
    // DFS를 통한 각각의 대륙 넘버링.
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (arr[i][j] == 1)
			{
				count++;
				DFS(i, j, count);
			}
		}
	}
	
    // 만약 대륙이 3 이하라면
    // 단일 대륙이라는 소리이기 때문에
    // 찾을 필요 없이 0을 리턴.
	if (count < 3)
	{
		printf("0\n");
		return 0;
	}

    // DFS를 통해 최단 거리를 찾는 알고리즘.
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			if (arr[i][j] != 0)
				Find(i, j, arr[i][j], 0);

        // 다 돌고나면 visit를 초기화.
		for (int k = 0; k < N; k++)
			for (int l = 0; l < N; l++)
				visit[k][l] = 0;
	}

	printf("%d\n", min);

	return 0;
}

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 1 0 0 0 0 1
0 0 0 0 1 0 0 0 0 1
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

output: 4

ehddml3 6년 전 1

그리고 왜 안되느냐는... DFS를 써서 그렇습니당.. BFS를 써보세용. DFS를 써도 되게하려면 visit 값을 적당히 큰수로 초기화시킨 다음에 visit[nx][ny]값보다 m+1이 작으면 그 값으로 바꿔주고 들어가는 방식으로 하면 될지도 모르겠네용

visit[x][y] 위치에 3이라는 depth로 이전에 도착을 했었는데 다른 경로로 2라는 depth값으로 접근하고 싶은데 이미 접근했었다고 접근이 차단당한다면...? 을 생각해보시면 될 것 같네용

whdnjqls456 6년 전 0

아~ 알겠습니다! 참고해서 다시 짜보겠습니다!

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

문제

문제

출처

ICPC

아.. 도와주십시오;;

whdnjqls456 6년 전 0

ehddml3 6년 전 1

ehddml3 6년 전 1

whdnjqls456 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말