🌞Algorithm/🔥Baekjoon

[Baekjoon] 26170_사과 빨리 먹기

뿌야._. 2024. 6. 21. 15:06

Silver II

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

< 사과 빨리 먹기 >

 

문제 풀이 

 

현재 위치에서 상하좌우로 이동하여 사과를 먹는다.

 

 my solution (Java)

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

public class _26170_ { // 사과 빨리 먹기
	static int arr[][], answer;
	static boolean visited[][];
	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;

		arr = new int[5][5];
		visited = new boolean[5][5];

		for (int i = 0; i < 5; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < 5; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		st = new StringTokenizer(bf.readLine());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		answer = Integer.MAX_VALUE;
		visited[r][c] = true;
		dfs(r, c, 0, 0);

		if (answer == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(answer);
		}
	}

	private static void dfs(int r, int c, int apple, int d) {
		if (apple == 3) {
			answer = Math.min(answer, d);
			return;
		}
		for (int i = 0; i < 4; i++) {
			int x = r + dx[i];
			int y = c + dy[i];
			if (x >= 0 && x < 5 && y >= 0 && y < 5 && !visited[x][y] && arr[x][y] != -1) {
				visited[x][y] = true;
				if (arr[x][y] == 1) {
					dfs(x, y, apple + 1, d + 1);
				} else {
					dfs(x, y, apple, d + 1);
				}
				visited[x][y] = false;
			}
		}
	}
}
변수)
arr : 보드 정보
visited : 방문 여부
r, c : 현재 위치
answer : 최소 이동 횟수

 

보드 정보를 입력받는다. 현재 위치를 입력받은 후 현재 위치를 방문 표시하고 dfs 함수를 호출한다. 호출 후 answer 값이 바뀌지 않았다면 사과 3개를 먹을 수 없는 것이므로 -1을 출력하고 그 외에는 answer 값을 출력한다.

 

dfs (int r, int c, int apple, int d)

만약 사과 3개를 먹었다면 answer 값을 최솟값으로 업데이트하고 종료한다.

 

상하좌우를 탐색하며 보드 범위 안이며 아직 방문하지 않았고 장애물이 있는 곳이 아니라면 방문 표시한다. 만약 이동한 곳에 사과가 있다면 dfs(이동 위치, 사과+1, 이동 횟수+1)을 호출한다. 사과가 없다면 dfs(이동 위치, 사과, 이동 횟수+1)을 호출한다. 모든 경우의 수를 다 탐색하기 위해 방문 표시를 다시 제거한다.



 

'🌞Algorithm > 🔥Baekjoon' 카테고리의 다른 글

[Baekjoon] 9204_체스  (0) 2024.06.25
[Baekjoon] 1474_밑 줄  (1) 2024.06.24
[Baekjoon] 2777_숫자 놀이  (0) 2024.06.20
[Baekjoon] 5002_도어맨  (0) 2024.06.19
[Baekjoon] 2072_오목  (0) 2024.06.18