글 읽기 - BFS 탐색 순서에도 차이가 있나요?

tjseocld 1년 전 0

안녕하세요! BFS로 문제를 풀 때 , 밑의 소스와 같이 이동할 좌표 값을 미리 선언해 두고 for문으로 돌아가면서 주변을 탐색하는 코드에서

탐색 순서에 따라 값이 바뀌는데 , Check 배열로 방문 확인도 확인도 하고 Queue에 들어가는 순서가 다를 수 있지만 , 이게 반례를 만들어 낼 수 있다는 게 이해하기 힘듭니다. 왜 탐색 순서에 따라 값이 바뀌는지 설명해 주실 분 계신가요?

추가 : BFS 가 양쪽으로 동일한 가중치를 뻗어가는 것은 이해를 했습니다. 다만 해당 코드에서 항상 최단 경로를 검사함에도 반례가 발생했습니다.

int coorX[] = {-1,0,0 , 1};
int coorY[] = {0,-1,1 , 0};
// 오답

int coorX[] = {-1,0,0 , 1};
int coorY[] = {0,1,-1 , 0};
// 오답

int coorX[] = {-1,0,1,0};
int coorY[] = {0,1,0,-1};
// 정답

// 코드
package backzoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class back_16236 {

	static int arr[][];
	static boolean check[][];
	static int size = 2;
	static int eatting = 0;
	static int N;
	
	static class Coordinate {
		int x;
		int y;
		int cnt;
		public Coordinate(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	
	public static Coordinate bfs(int startX , int startY) {
		int coorX[] = {-1,0,1 , 0};
		int coorY[] = {0,1,0 , -1};
		
		Queue<Coordinate> queue = new LinkedList<>();
		queue.add(new Coordinate(startX, startY, 0));

		Coordinate finded = null;
		boolean isFind = false;
		
		while(!queue.isEmpty()) {
			Coordinate data = queue.poll();
			
			for(int i = 0; i < 4; i++) {
				int X = coorX[i] + data.x;
				int Y = coorY[i] + data.y;
				int CNT = data.cnt + 1;
				if(X < 0 || X >= N || Y < 0 || Y >= N) continue;

				if(arr[Y][X] < size && arr[Y][X] >= 1 && arr[Y][X] <= 6 && !check[Y][X]) { // 먹기
					if(isFind) { // 값이 정해졌을 때
						if(finded.cnt < CNT && arr[Y][X] <= size) continue; // 거리가 길면 패스
						if(finded.cnt > CNT) { // 거리가 더 짧다?
							finded = new Coordinate(X, Y, CNT);
						} else if(finded.y > Y) {
							finded = new Coordinate(X, Y, CNT); // 더 높은것 찾기
						} else if (finded.x > X) {
							finded = new Coordinate(X, Y, CNT); // 더 왼쪽에 있는것 찾기
						}
					} else {
						finded = new Coordinate(X, Y, CNT);
						isFind = true;
						check[Y][X] = true;
					}
				}
				
				if(arr[Y][X] <= size && !check[Y][X]) { // 확산
					check[Y][X] = true;
					queue.add(new Coordinate(X, Y, CNT));
				}
			}
			
		}
		
		return finded;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		arr = new int[N][N];
		check = new boolean[N][N];
		int startX = 0 , startY = 0;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine() , " ");
			for(int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j] == 9) {
					startX = j;
					startY = i;
					arr[startY][startX] = 0;
				}
			}
		}
		
		int resultCnt = 0;
		check = new boolean[N][N];
		
		Coordinate result = new Coordinate(startX , startY , 0);
		
		while(true) {
			result = bfs(result.x , result.y);
			if(result == null) break;
			resultCnt += result.cnt;
			
			arr[result.y][result.x] = 0;
			eatting++;
			if(size <= eatting) {
				eatting = 0;
				size++;
			}
			
			check = new boolean[N][N];
		}
		System.out.println(resultCnt);
	}

}

pill27211 1년 전 2

어느 문제인지 모르겠지만, 각 탐색 방향에 대해 가중치가 동일함이 보장 되나요 ?

BFS는 기본적으로 모든 간선이 동일한 가중치를 갖는 그래프에선 항상 최단경로를 보장합니다.

tjseocld 1년 전 0

수정했습니다. @pill27211 님이 설명해주신 것은 이해가 됐습니다. 다만 if문을 통해 최소 값을 탐색하지만 반례가 발생하는 이유를 찾을 수 없었습니다.

ufshg 1년 전 1

흠...잘 모르겠네요.

제가 예전에 통과한 코드는 dy = 1 -1 0 0, dx = 0 0 1 -1이었습니다. 즉 상하좌우지요.

dy dx따라 답이 다르게 되는 이유가 뭘까요?

ufshg 1년 전 0

int coorX[] = {-1,0,0 , 1};

int coorY[] = {0,-1,1 , 0};

작성자분이 적어두신 오답뜨는 dx dy를 제 코드에 적용해보았는데 저는 통과합니다.

pill27211 1년 전 5

아기 상어 문제같은 경우에는, 거리는 같으나 우선순위의 차이가 존재 합니다.

결론부터 말씀 드리면, dx[]와 dy[]의 여부보다, 이하 로직에서의 조건 처리가 더 중요합니다.(아래 로직에서의 조건 분기가 완벽하다면, dx[], dy[]는 정답 여부와 상관 없습니다)

아기 상어의 이동을 결정하는 데엔

제일 우선적으로 '거리' 그 다음엔 '행' 그 다음엔 '열' 순서로 우선순위를 갖습니다.

바로 이것에 대해 어떻게 처리 하는지(큐 2개 사용, 우선순위 큐 사용, 큐에 삽입 순서 등등)가 문제이지, dx[], dy[]의 순서는 중요치 않습니다.

tjseocld 1년 전 2

자세히 살펴본 결과 방향 순서 문제가 아닌 구현 실수로 우연히 정답이 맞게 나왔던 것입니다. 답변해 주신 분들 덕분에 해결할 수 있었습니다. :) @pill27211 @ufshg

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

문제

문제

출처

ICPC

BFS 탐색 순서에도 차이가 있나요?

tjseocld 1년 전 0

pill27211 1년 전 2

tjseocld 1년 전 0

ufshg 1년 전 1

ufshg 1년 전 0

pill27211 1년 전 5

tjseocld 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말