[Baekjoon] 15558_점프 게임

Silver I

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

---

< 점프 게임 >

 

문제 풀이

 

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 _15558_ { // 점프 게임
	static int arr[][], n, k;
	static boolean visited[][], flag;
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		n=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		
		arr=new int[2][n];
		visited=new boolean[2][n];
		flag=false;
		
		String str=bf.readLine();
		String str2=bf.readLine();
		for(int i=0; i<n; i++) {
			arr[0][i]=str.charAt(i)-'0';
			if(arr[0][i]==0) visited[0][i]=true;
			arr[1][i]=str2.charAt(i)-'0';
			if(arr[1][i]==0) visited[1][i]=true;
		}
		search(0,0, 0);
		
		if(flag) System.out.println(1);
		else System.out.println(0);
	}

	private static void search(int x , int y, int i) {
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int [] {x,y,i});
		
		visited[0][0]=true;
		
		while(!queue.isEmpty()) {
			int[] temp=queue.poll();
			if(temp[1]+1 > n || temp[1]+k >= n) { // 종료 조건
				flag=true;
				break;
			}
			if(!visited[temp[0]][temp[1]+1]) { // 한 칸 앞 이동
				visited[temp[0]][temp[1]+1]=true;
				queue.add(new int[] {temp[0], temp[1]+1, temp[2]+1});
			}
			if(temp[1]-1>=0 && !visited[temp[0]][temp[1]-1] && temp[1]-1>temp[2]) { // 한 칸 뒤로 이동
				visited[temp[0]][temp[1]-1]=true;
				queue.add(new int[] {temp[0], temp[1]-1, temp[2]+1});
			}
			// 반대편 줄로 점프
			if(temp[0]==0) {
				if(!visited[1][temp[1]+k]) {
					visited[1][temp[1]+k]=true;
					queue.add(new int[] {1,temp[1]+k, temp[2]+1});
				}
			}else if(temp[0]==1) {
				if(!visited[0][temp[1]+k]) {
					visited[0][temp[1]+k]=true;
					queue.add(new int[] {0, temp[1]+k, temp[2]+1});
				}
			}
		}
	}
}

 

Main

- N과 K 입력

- 왼쪽 줄과 오른쪽 줄을 입력받으면서 위험한 칸인 0이면 방문 여부를 true로 설정해 준다.

- search 함수 호출

- 게임을 클리어할 수 있으면 1을 출력, 클리어할 수 없으면 0을 출력

 

Search

- queue에 [x좌표, y좌표, 시간]을 넣어준다.

- queue가 빌 때까지 반복하며 조건을 설정해 준다.

  1) n번 칸보다 더 큰 칸으로 이동하는 경우 flag를 true로 설정한 후 종료해 준다. 

  2) 한 칸 앞으로 이동하는 경우 아직 방문하지 않은 곳이면 갈 수 있는 곳이므로 이동 후 queue에 추가해 준다.

  3) 한 칸 뒤로 이동하는 경우 지도에 존재하는 칸이며 아직 방문하지 않았고, 아직 없어지지 않은 칸이면 이동 후 queue에 추가해 준다.

  4) 반대편 줄로 이동하는 경우 아직 방문하지 않은 곳이면 갈 수 있는 곳이므로 이동 후 queue에 추가해 준다.

---

생각🤔

 

 

---