[Baekjoon] 6004_The Chivalrous Cow

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

---

< The Chivalrous Cow >

 

문제 풀이 

 

bfs 알고리즘을 활용한다.

 

 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 _6004_ { // The Chivalrous Cow
	static int dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
	static int dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
	static boolean arr[][];
    
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
        
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
        
		arr = new boolean[y][x];
		int x1 = -1, y1 = -1, x2 = -1, y2 = -1;
		for (int i = 0; i < y; i++) {
			String str = bf.readLine();
			for (int j = 0; j < x; j++) {
				if (str.charAt(j) == '*') {
					arr[i][j] = true;
				} else if (str.charAt(j) == 'K') {
					x1 = i;
					y1 = j;
				} else if (str.charAt(j) == 'H') {
					x2 = i;
					y2 = j;
				}
			}
		}
		System.out.println(bfs(x1, y1, x2, y2));
	}
    
	private static int bfs(int x1, int y1, int x2, int y2) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { x1, y1, 0 });
        
		arr[x1][y1] = true;
        
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 8; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && !arr[x][y]) {
					if (x == x2 && y == y2) {
						return temp[2] + 1;
					}
					arr[x][y] = true;
					queue.add(new int[] { x, y, temp[2] + 1 });
				}
			}
		}
		return -1;
	}
}

변수)
x, y : 배열 크기
arr : 방문 여부
x1, y1, x2, y2 : 출발 위치, 도착 위치
dx, dy : 이동 방향

 

배열 크기를 입력받아 배열 크기만큼 정보를 입력받는다. 장애물 *인 경우 true로 저장하고 시작 위치 K인 경우 x1, y1에 위치 저장, 도착 위치 H인 경우 x2, y2에 위치를 저장한다. bfs 함수를 호출한 결과를 출력한다.

 

bfs(int x1, int y1, int x2, int y2)

Queue에 시작 위치와 이동 횟수를 저장하며 시작 위치를 방문처리한다. Queue가 빌 때까지 다음 과정을 반복한다.

1) Queue poll

2) 8방향으로 탐색 후 배열 범위 안이며 아직 방문하지 않은 곳이라면 방문 표시 및 Queue에 추가. 만약 이동 위치가 도착 위치라면 temp[2]+1을 반환한다.

 

---

---