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