글 읽기 - 그래프 최장거리 알고리즘을 적용못하는 이유는 뭘까요?

qkfskan82 3년 전 1

처음에 각 L 덩어리 별로 아무곳에서나 bfs 돌려서 최장거리를 시작점들로 잡고 (그래프 최장거리 찾는 알고리즘 응용),

그 시작점들로 다시 최장거리 answer 찾는 방식으로 했더니 틀려서...

그냥 브루트포스로 통과했습니다.

제 구현에서 문제가 있었던 건지, 아니면 알고리즘 적으로 불가능했던건지 궁금합니다.

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 Main{
	static StringTokenizer st;
	static int N, M, answer = 0;
	static char[][] map;
	static boolean[][] visit;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new char[N][M];
		visit = new boolean[N][M];

		for (int n = 0; n < N; n++) {
			String str = br.readLine();
			for (int m = 0; m < M; m++) {
				map[n][m] = str.charAt(m);
			}
		} //map 잡아주기

		Queue<int[]> queue1 = new LinkedList<>();
		Queue<int[]> queue2 = new LinkedList<>();
		int x = 0, y = 0;
        //BFS 돌릴 Queue 두개 미리 만들기
		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (!visit[n][m] && map[n][m] == 'L') {
                    //L덩어리를 찾았을시 스타트
					visit[n][m] = true;
					queue1.offer(new int[] { n, m });

					while (!queue1.isEmpty()) {
						x = queue1.peek()[0];
						y = queue1.poll()[1];

						for (int i = 0; i < 4; i++) {
							int nX = x + delta[i][0];
							int nY = y + delta[i][1];

							if (isIn(nX, nY) && !visit[nX][nY] && map[nX][nY] == 'L') {
								visit[nX][nY] = true;
								queue1.offer(new int[] { nX, nY });
							}
						}
					}//bfs 돌면서 덩어리 완탐, 이때 가장 마지막까지 큐에 있던 좌표
                    //임의의 점에서 가장 먼 좌표가 최장거리의 양 끝단중 하나 (맞을까요?)
					queue2.offer(new int[] { x, y, 0 });
				}
			}
		}
		
		visit = new boolean[N][M];
		//위에서 잡아둔 최장거리일 가능성이 있는 시작점들 가지고 다시 bfs
        //덩어리마다 하나씩만 시작하고 서로 접근이 불가능하니 따로 캐치는 안함
		while (!queue2.isEmpty()) {
			int[] now = queue2.poll();
			x = now[0];
			y = now[1];
			int l = now[2];
			answer = Math.max(l, answer);

			if (l == 0) {
				visit[x][y] = true;
			}//visit 체크가 초기화되었으니 시작점인 경우만 체크해주기

			for (int i = 0; i < 4; i++) {
				int nX = x + delta[i][0];
				int nY = y + delta[i][1];

				if (isIn(nX, nY) && !visit[nX][nY] && map[nX][nY] == 'L') {
					visit[nX][nY] = true;
					queue2.offer(new int[] { nX, nY, l + 1 });
				}
			}
		}

		System.out.println(answer);
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < M) {
			return true;
		}

		return false;
	}
}

qkfskan82 2년 전 5

제가 쓰려고 했던 알고리즘은 그래프가 아니라 MST의 지름 구하는 알고리즘이었고,

그래프에 적용 못하는 이유는 그래프에 루프가 존재하는 경우에 예외가 발생하기 때문입니다....

혹시나 비슷한 궁금증을 가지는 분이 생길까 셀프답변 달아봅니다.

9개월 전의 나는 이렇게나 멍청했단 말인가

mmj9808 1년 전 0

저도 똑같이 생각하고 풀었는데 그래프에 루프가 존재할 경우에는 최장거리 알고리즘을 적용할 수 없었군요!

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

문제

문제

출처

ICPC

그래프 최장거리 알고리즘을 적용못하는 이유는 뭘까요?

qkfskan82 3년 전 1

qkfskan82 2년 전 5

mmj9808 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말