알고리즘 스터디 3주차 - 1

이강민·2024년 8월 3일

Kernel360 알고리즘

커널360

목록 보기

21/56

16173

알고리즘 : DFS, BFS, 브루트포스
난이도 : 실버4

문제

16173

접근

게임의 이해
- 젤리는 1,1에서 시작한다.
- 젤리가 이동해야하는 칸 수는 현재 칸에 적혀있다.
- 무조건 현재 칸 수 만큼 이동해야한다.
어떻게 풀까?
- 표로 표현되는 문제
  - 그래프 -> DFS, BFS
  - DFS로 문제를 풀어도 시간초과가 나오지 않을 듯 (2~3사이의 크기)
DFS는 어떻게 적용시키지? 재귀호출 방식으로

가정

DFS로 문제를 해결 할 수 있을 것이다.
만약 시간 초과가 발생하면 BFS를 고려한다.

풀어보기

package org.example;

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

public class Main {
	static int gameSize;
	static int[][] gameBoard;
	static boolean[][] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		gameSize = Integer.parseInt(bufferedReader.readLine());
		gameBoard = new int[gameSize][gameSize];
		visited = new boolean[gameSize][gameSize];
		for(int i = 0; i < gameSize; i++) {
			String[] temp = bufferedReader.readLine().split(" ");
			for (int j = 0; j < gameSize; j++) {
				gameBoard[i][j] = Integer.parseInt(temp[j]);
			}
		}
		DFS(0,0);
		if(visited[gameSize-1][gameSize-1]){
			System.out.println("HaruHaru");
		}
		if(!visited[gameSize-1][gameSize-1]){
			System.out.println("Hing");
		}
	}
	//DFS
	public static void DFS(int x,  int y){
		if(x < 0 ) return;
		if(y < 0 ) return;
		if(x > gameSize - 1 ) return;
		if(y > gameSize - 1 ) return;
		if(visited[x][y]) return;

		visited[x][y] = true;
		DFS(x+gameBoard[x][y], y);
		DFS(x, y +gameBoard[x][y]);
	}
}