[Baekjoon] 26169_세 번 이내에 사과를 먹자

Silver III

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

---

< 세 번 이내에 사과를 먹자 >

 

문제 풀이

 

dfs로 탐색하면서 세 번의 이동을 했을 때 사과를 2개 이상 먹을 수 있으면 종료한다.

 

 

 

 my solution (Java)

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

public class _26169_ { // 세 번 이내에 사과를 먹자
	static int arr[][];
	static boolean result, 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());
				if(arr[i][j]==-1) visited[i][j]=true;
			}
		}

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

		result = false;
		int num=0;
		if(arr[r][c]==1) num+=1;
		visited[r][c]=true;
		dfs(r, c, 0, num);

		if (result)
			System.out.println("1");
		else
			System.out.println("0");

	}

	private static void dfs(int r, int c, int cnt, int num) {
		if (cnt == 3) {
			if (num >= 2) {
				result = true;
				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]) {
				visited[x][y]=true;
				if(arr[x][y]==1) {
					dfs(x,y,cnt+1, num+1);
				}else {
					dfs(x,y,cnt+1, num);
				}
				visited[x][y]=false;
			}
		}
	}
}

 

Main

-  arr : 보드의 정보 입력

- visited: 방문 여부 표시 (장애물이 있는 격자는 방문한 것으로 표시)

- 현재 위치 r, c 입력

- 만약 주어진 현재 위치가 사과가 있는 칸인지 확인 후 사과가 있는 칸이라면 num 값 증가 

  현재 위치는 방문한 것이므로 방문 표시 및 dfs 함수 호출

- result 값이 true면 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으므로 1 출력. 사과를 2개 이상 먹을 수 없다면 0 출력.

 

dfs(현재 시작 위치 r, c, 이동 횟수, 먹은 사과 수)

- 종료 조건 : 3번 이동했으며 사과를 2개 이상 먹었다면 result를 true로 저장 후 종료

- 상하좌우를 탐색하며 보드 범위 안이며 아직 방문하지 않았다면 방문 표시/ 이동한 칸이 사과가 있는 칸이라면 이동 횟수 +1, 사과 수 +1로 dfs 함수 호출 but 사과가 없는 칸이라면 이동 횟수 +1 후 dfs 호출 / dfs 함수 호출 후 다음 탐색을 위해 방문 표시를 false로 저장

 

---

마무리🤔

 

---