[Baekjoon] 5931_Cow Beauty Pageant

문제(출처: https://www.acmicpc.net/problem/5931)

---

< Cow Beauty Pageant >

 

문제 풀이 

 

1) bfs 알고리즘을 활용하여 한쪽 spot의 위치를 Queue에 저장한다.

2) 1번에서 찾은 spot의 위치들을 저장한 Queue를 활용하여 bfs 탐색하며 다른 spot까지의 최소 거리를 찾는다.

 

 my solution (Java)

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 _5931_ { // Cow Beauty Pageant
	static int result[][], answer;
	static boolean visited[][];
	static Queue<int[]> position;
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		visited = new boolean[n][m];
		result = new int[n][m];
		int startX = -1, startY = -1;
		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < m; j++) {
				if (str.charAt(j) == 'X') {
					visited[i][j] = true;
				}
				if (visited[i][j] && startX == -1 && startY == -1) {
					startX = i;
					startY = j;
				}
				result[i][j] = -1;
			}
		}
		position = new LinkedList<>();
		findSpot(startX, startY);
		answer = Integer.MAX_VALUE;
		bfs();
		System.out.println(answer);
	}
	private static void bfs() {
		while (!position.isEmpty()) {
			int temp[] = position.poll();
			for (int i = 0; i < 4; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < result.length && y >= 0 && y < result[0].length
						&& (result[x][y] == -1 || result[temp[0]][temp[1]] + 1 < result[x][y])) {
					if (result[temp[0]][temp[1]] > 0 && visited[x][y]) {
						answer = Math.min(answer, result[temp[0]][temp[1]]);
						break;
					}
					result[x][y] = result[temp[0]][temp[1]] + 1;
					position.add(new int[] { x, y });
				}
			}
		}
	}
	private static void findSpot(int startX, int startY) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { startX, startY });
		position.add(new int[] { startX, startY });
		visited[startX][startY] = false;
		result[startX][startY] = 0;
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < visited.length && y >= 0 && y < visited[0].length && visited[x][y]) {
					visited[x][y] = false;
					result[x][y] = 0;
					queue.add(new int[] { x, y });
					position.add(new int[] { x, y });
				}
			}
		}
	}
}

 

변수)
n, m : 배열 크기
visited : spot 표시
result : spot을 연결하는 최소 거리
startX, startY : 한쪽 spot의 시작점
position : startX, startY를 시작으로 하는 한쪽 spot의 위치들
answer : 최소 거리

 

배열 크기를 입력받아 배열 크기만큼 정보를 입력받으며 result 값을 -1로 초기화한다. 이때 정보값이 X라면 visited를 true로 저장하며 처음 찾은 spot 위치라면 startX와 startY를 업데이트한다. 

findSpot 함수를 호출하여 startX와 startY를 시작점으로 하는 spot의 위치들을 Queue에 저장한다.

bfs 함수를 호출하며 Queue에 저장한 값들을 시작점으로 하여 다른 spot까지의 최소 거리를 찾는다.

최종 answer을 출력한다.

 

bfs()

Queue가 빌 때까지 다음 과정을 반복한다.

1) Queue poll

2) 4방향으로 탐색 후 배열 범위 안이며 result 값이 -1이거나 최솟값으로 업데이트 가능하다면 result 업데이트 및 queue에 추가한다. 이때 다른 spot에 도착했다면 answer을 최솟값으로 업데이트하고 종료한다. 

 

findSpot(int startX, int startY)

queue와 position Queue에 각각 시작 위치를 저장한다. 시작 위치의 visited를 false로 저장하고, result도 0으로 저장한다. queue가 빌 때까지 다음 과정을 반복한다.

1) queue poll

2) 4방향으로 탐색 후 배열 범위 안이며 visited가 true라면 visited를 false, result를 0으로 저장하고 각 queue와 position에 위치를 저장한다.

---

---