메뉴 닫기

[BOJ] 1600 말이 되고픈 원숭이 + 반례

1600번: 말이 되고픈 원숭이 (acmicpc.net)

BFS 문제

문제의 조건을 잘 읽어야 한다.
가로 세로도 헷갈리게 되어있어서 주의해야한다.
원숭이의 동작수의 최솟값을 출력하고, 도착점까지 갈 수 없는 경우에는 -1을 출력해줘야 한다.
또 visited 배열을 사용할 때 평범한 bfs와 달리 말처럼 이동한 경우가 있기 때문에 2차원->3차원배열로 선언하여
중복문제를 해결하였다.

다 풀다고 생각했는데 100%에서 틀렸습니다 라고 떠서 확인을 해보니
시작하자마자 도착점에 가있는 경우를 고려하지 않아서 발생한 문제였다.
result 를 -1로 초기화해서 처리해줬다.

반례

1
1 1 
0

답 = 0

1
3 2
0 1 1
1 1 0

답 = 1

1
3 2 
0 0 0
0 0 1

답 = -1

1
3 3
0 0 0
0 1 1
1 1 0 

답 = 2
package com.algo.boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ1600MtoH {
	private static int[][] map;
	private static boolean[][][] visited;
	private static int R,C,K;
	private static int[] dhx = {-1, -2, -1, -2, 1, 2, 1, 2};
	private static int[] dhy = {-2, -1, 2, 1, -2, -1, 2, 1};
	private static int[] dx = {-1, 1, 0, 0};
	private static int[] dy = {0, 0, -1, 1};
	static int result=-1;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		map = new int[R][C];  // map 정보 저장
		visited = new boolean[R][C][K+1]; //bfs 경로 저장을 위한 3차원 visited
		for (int i = 0; i < R; i++) {
			st =  new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				map[i][j] =Integer.parseInt(st.nextToken());
			}
		}//for
		jump();

	}
	private static void jump() {
		Queue<int[]> q = new LinkedList<int[]>(); //bfs를 위한 큐
		q.add(new int[] {0,0,0,0});	// x,y,k,tr 을 큐에 배열로 전달
		while (!q.isEmpty()) {
			int[] data = q.poll();
			int x = data[0];
			int y = data[1];
			int k = data[2];
			int tr = data[3];
			if(x == R-1 && y == C-1) { //마지막에 도착한 경우 
				result = tr;
				break; //bfs이기 때문에 레벨 즉 이동횟수가 동일하
			}
			if(k<K) { //말처럼 이동가능한 회수가 남은 경우
				for (int i = 0; i < 8; i++) {
					int nx = x+dhx[i];
					int ny = y+dhy[i];
					if(nx<0|| ny<0 || nx >= R || ny >=C) continue;
					if(map[nx][ny]==1)continue;
					if(visited[nx][ny][k+1]) continue;
					visited[nx][ny][k+1]=true;
					q.add(new int[] {nx,ny,k+1,tr+1});
				}
			}
			for (int i = 0; i < 4; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx<0|| ny<0 || nx >= R || ny >=C) continue;
				if(map[nx][ny]==1)continue;
				if(visited[nx][ny][k]) continue;
				visited[nx][ny][k]=true;
				q.add(new int[] {nx,ny,k,tr+1});
			}

		}
			System.out.print(result);
	}

}

느낀점

  1. BFS 를 하려면 visited를 써야한다.
    이건 당연한건데, 코드를 짜다보니 이동하는 로직에만 집중하다보니 빠뜨리고 말았다.
  2. 문제의 조건을 끝까지 정확하게 읽자
    대충 문제를 제대로 안읽고, 코드를 짜기 시작할 때, 오늘과 같은 일이 생기는 것 같다.
    어떤 방법으로 풀어야 할지 대충 느낌이 있는 문제일 수록, 문제의 조건을 정확히 읽어야 겠다.

Related Posts

답글 남기기

이메일 주소는 공개되지 않습니다.

%d 블로거가 이것을 좋아합니다: