[Baekjoon] 6191_Cows on Skates

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

---

< Cows on Skates >

 

문제 풀이 

 

bfs 알고리즘을 활용하여 이동 경로를 저장하며 도착 지점까지 이동한다.

 

 

 my solution (Java)

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

public class _6191_ { // Cows on Skates
	static boolean arr[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
    
	static class Info {
		int x;
		int y;
		ArrayList<int[]> list;
        
		public Info(int x, int y, ArrayList<int[]> list) {
			this.x = x;
			this.y = y;
			this.list = list;
		}
	}
    
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());
        
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
        
		arr = new boolean[r][c];
		for (int i = 0; i < r; i++) {
			String str = bf.readLine();
			for (int j = 0; j < c; j++) {
				if (str.charAt(j) == '*') {
					arr[i][j] = true;
				}
			}
		}
        
		ArrayList<int[]> result = bfs();
        
		for (int[] answer : result) {
			bw.write(answer[0] + " " + answer[1] + "\n");
		}
		bw.write(r + " " + c);
		bw.flush();
	}
	private static ArrayList<int[]> bfs() {
		Queue<Info> queue = new LinkedList<>();
		ArrayList<int[]> list = new ArrayList<>();
		list.add(new int[] { 1, 1 });
		queue.add(new Info(0, 0, list));
        
		arr[0][0] = true;
        
		while (!queue.isEmpty()) {
			Info info = queue.poll();
			for (int i = 0; i < 4; i++) {
				int x = info.x + dx[i];
				int y = info.y + dy[i];
				if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && !arr[x][y]) {
					if (x == arr.length - 1 && y == arr[0].length - 1) {
						return info.list;
					}
					arr[x][y] = true;
					ArrayList<int[]> temp = new ArrayList<>(info.list);
					temp.add(new int[] { x + 1, y + 1 });
					queue.add(new Info(x, y, temp));
				}
			}
		}
		return null;
	}
}

변수)
dx, dy : 이동 방향
arr : 배열
r, c : 배열 크기
result : 도착 지점까지 이동 경로

 

Info

현재 위치 x, y 좌표와 이동 경로 ArrayList를 변수로 가짐

 

Main

배열 크기를 입력받아 배열 크기만큼 정보를 입력받는다. 배열 값이 *라면 arr 배열에 true로 저장한다. bfs 함수를 호출하여 반환 값인 ArrayList와 도착 위치를 출력한다.

 

bfs()

Queue에 Info 객체를 저장하고 출발 위치 (0,0)을 방문처리한다. Queue가 빌 때까지 다음 과정을 반복한다.

1) Queue poll

2) 4방향으로 탐색 후 배열 범위 안이며 아직 방문하지 않은 곳이라면 방문 표시 및 이동 경로 추가하여 Queue에 추가. 만약 도착 위치라면 이동 경로 반환

---

---