[백준] 1600번:말이 되고픈 원숭이 (Java 자바)

[백준] 1600번:말이 되고픈 원숭이 (Java 자바)

반응형

문제

https://www.acmicpc.net/problem/1600

풀이 및 소스코드

왜 말이 되고픈지 모르겠당..

넘 어려웠다.

k별로도 방문체크를 해줘야했기때문에 인생 최초로 3차배열에 방문표시를 해줬다.

이 때문에 푸는 게 오래걸린 것 같다.

처음에 dfs로 풀려고 했으나, 시간초과가 났다.

bfs로 바꿨는데 6%에서 자꾸 틀렸다고 했다.

현재 좌표에 대한 k_cnt 값을 고려해주지 않고, 그저 k 만 넘지 않았으면 시간 비교를 해줬기 때문에 논리적 오류가 생긴 것 같다.

6%에서 틀렸습니다. 가 뜨는 사람들은 봐야할 반례

1

5 5

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 1 1

0 0 0 1 0

정답 : 6

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; class Main { static int n,m,k; static int[][] map; static boolean[][][] v; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; k = Integer.parseInt(br.readLine()); st = new StringTokenizer(br.readLine()); m = Integer.parseInt(st.nextToken()); n = Integer.parseInt(st.nextToken()); v = new boolean[n][m][k+1]; //k카운트에 대해 방문표시 할 배열. n행 m열 말의 이동을 k번 했다. map = new int[n][m]; for(int i=0;i q = new PriorityQueue<>(); int[] dx = {1, 0, -1, 0, -2, -1, 1, 2, -2, -1, 1, 2}; int[] dy = {0, 1, 0, -1, 1, 2, 2, 1, -1, -2, -2, -1}; //4~11 : 말처럼 q.add(new node(0, 0, 0, 0)); v[0][0][0] = true; while(!q.isEmpty()) { node now = q.poll(); int x = now.x; int y = now.y; int time = now.time; int k_cnt = now.k_cnt; if(x==n-1&&y;==m-1) return time; for(int i=0;i<12;i++) { int nowx = x+dx[i]; int nowy = y+dy[i]; if(nowx<0||nowy<0||nowx>=n||nowy>=m) continue; if(map[nowx][nowy] == 1) continue; if(i>=4&&k;_cnt>=k) break; if(i>=4) { if(!v[nowx][nowy][k_cnt+1]) { q.add(new node(nowx, nowy, time+1, k_cnt+1)); v[nowx][nowy][k_cnt+1] = true; } }else { if(!v[nowx][nowy][k_cnt]) { v[nowx][nowy][k_cnt] = true; q.add(new node(nowx, nowy, time+1, k_cnt)); } } } } return -1; } } class node implements Comparable{ int x,y,time,k_cnt; public node(int x, int y, int time, int k_cnt) { super(); this.x = x; this.y = y; this.time = time; this.k_cnt = k_cnt; } @Override public int compareTo(node o) { if(o.time==this.time) { return this.k_cnt-o.k_cnt; } return this.time-o.time; } }

반응형

from http://jainn.tistory.com/266 by ccl(A) rewrite - 2021-09-16 05:01:39