글 읽기 - BFS를 이용해 전탐색시 시간초과 발생

woodyu995 6년 전 0

안녕하세요

다음과 같은코드의 형태로 BFS를 이용하여 문제를 푸는데 시간초과가 발생합니다.

혹시 이문제에 대해서 아시는 분 있으시면 답변좀 부탁드려도 될까요?

제가 검색해본 결과로는 구글검색을 통해 다음과 같은 블로그의 코드를 봤는데요

http://blog.naver.com/PostView...

여기에 나와있는 BFS와 제 BFS코드의 차이를 잘 모르겠습니다.

그리고 제생각으로는 R의 최대값이 3이고 C의 최대값이 250이라면 시간복잡도를 대략 계산해봐도 시간초과가 날거 같진 않아서요

고수분들 도움 부탁드립니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//BFS 전탐색 -> 시간초과 발생
public class Main {
	static int SHEEP = 0;
	static int WOLF = 1;

	public static void main(String[] args) {
	
		Scanner sc = new Scanner(System.in);
		int sheep = 0;
		int wolf = 0;
		int N = sc.nextInt();
		int M = sc.nextInt();
		char[][] map = new char[N][M];
		int animal[] = new int[2];

		Main test = new Main();
		sc.nextLine();
		for (int i = 0; i < N; i++) {
			char[] temp = sc.nextLine().toCharArray();
			for (int j = 0; j < M; j++) {
				map[i][j] = temp[j];

			}
		}
		sc.close();
//		long start = System.currentTimeMillis();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j] != '#' && map[i][j] != '.'){
					animal = test.calc(map, i, j);
					if (animal[SHEEP] > animal[WOLF]) {
						sheep += animal[SHEEP];
					} else {
						wolf += animal[WOLF];
					}
				}
			}
		}
		System.out.println(sheep + " " + wolf);
//		long end = System.currentTimeMillis();

//		System.out.println( "실행 시간 : " + ( end - start )/1000.0 );
	}

	public int[] calc(char[][] map, int i, int j) {
		Queue<Integer> queue = new LinkedList<Integer>();
		int[] animal = new int[2];
		//위 아래 오른쪽 왼쪽
		int[] offSetX = {-1, 1, 0, 0};
		int[] offSetY = {0, 0, 1, -1};
		queue.add(i);
		queue.add(j);
		while (!queue.isEmpty()) {
			int r = queue.poll();
			int c = queue.poll();

			if (map[r][c] == 'v') {
				animal[WOLF]++;
			}
			if (map[r][c] == 'o') {
				animal[SHEEP]++;
			}
			map[r][c] = '#';

			for(int z = 0; z < 4; z++){
				int tempX = r+offSetX[z];
				int tempY = c+offSetY[z];
				if(tempX >= 0 && tempX < map.length && tempY >= 0 && tempY < map[0].length){
					if(map[tempX][tempY] != '#'){
						queue.add(tempX);
						queue.add(tempY);
					}
				}
			}
		}
		return animal;
	}
}

bupjae 6년 전 0

한 번 방문했던 좌표를 표시하는 알고리즘이 불완전하기 때문에 같은 좌표를 반복적으로 방문하는 걸로 보입니다.

woodyu995 6년 전 0

bupjae님 감사합니다. 큐에 넣기전 방문표시 하는 방식으로 해서 해결하였습니다.

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

문제

문제

출처

ICPC

BFS를 이용해 전탐색시 시간초과 발생

woodyu995 6년 전 0

bupjae 6년 전 0

woodyu995 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말