문제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
| 1초 | 256 MB | 2373 | 545 | 412 | 21.950% |
용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.
마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈를 반드시 하고 싶은 용사는 T시간 내에 반드시 공주님이 있는 곳으로 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸리며, 공주님이 있는 곳에 정확히 T초만에 도달하는 경우도, 구출 할 수 있다.
성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.
우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.
입력
첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 5000)
두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.
출력
용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.
만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "`Fail`"을 출력한다.
풀이 (DP)
path라는 배열을 만들어, board(미로) 에서 매 칸마다의 최소 움직임을 저장해둔다.
2중for문으로 미로의 처음부터 끝까지 돌린다.
이때 역순으로 움직여야 할 상황이 발생하므로, 이 이중for문을 t번 반복한다.
마지막에 칼을 찾았을 때의 경로랑 비교해서 정답 출력
코드 (DP)
import java.io.IOException;
public class Main {
public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
public static int[][] board;
public static int[][] path;
public static int ans = 99999;
static int n;
static int m;
static int t;
static int swordx;
static int swordy;
public static void main(String[] args) throws IOException {
String s = br.readLine().trim();
String str1[] = s.split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
t = Integer.parseInt(str1[2]);
path = new int[n+2][m+2];
//경로를 저장할 2차원 배열
initBoard(path, ans);
board = new int[n+2][m+2];
//진짜 판은 미리 1로 감싸기
initBoard(board,1);
for(int i=1;i<n+1;i++){
s = br.readLine().trim();
str1 = s.split(" ");
for(int j=1; j<m+1; j++) {
board[i][j] = Integer.parseInt(str1[j-1]);
//칼 찾을때는 그 좌표만 저장해두고, 0으로 넣기
if(board[i][j] == 2) {
swordx = j;
swordy = i;
board[i][j] = 0;
}
}
}
//n+m보다 t가 작으면 절대 못함.
if(t < n+m-2){
System.out.println("Fail");
return;
}
//findpath를 t번 돌림 (왜냐면 findpath할때 ↑→로 움직여야 할 경우가 발생하면 다시 돌려줘야 하므로.)
for(int a =0; a<t; a++) {
findpath();
}
//칼을 찾았을때랑 비교
if(path[swordy][swordx] < t ) {
path[n][m] = Math.min(path[swordy][swordx] + n-swordy+m-swordx, path[n][m]);
}
//정답 출력하기
if(path[n][m] > t) {
System.out.println("Fail");
}
else {
System.out.println(path[n][m]);
}
}
public static void findpath() {
path[1][1] = 0;
for(int y =1; y < n+1; y++) {
for(int x=1; x<m+1; x++) {
//벽이어도 나가리
if(board[y][x] == 1) continue;
//t보다 커도 나가리
if(path[y][x] > t) continue;
//만약 아래로 한칸 내려간게 현재보다 거리가 멀면
if((board[y+1][x] == 0) && (path[y][x] < path[y+1][x])) {
path[y+1][x] = path[y][x]+1;
}
//마찬가지로 밑으로 내려간게 현재보다 거리가 멀면
if((board[y][x+1] == 0) && (path[y][x] < path[y][x+1])) {
path[y][x+1] = path[y][x]+1;
}
//이전에 지나왔어야 할 함수가 현재보다 숫자가 크면 현재에서 역행했다고 생각하기.
if((board[y-1][x] == 0) && (path[y][x] < path[y-1][x])) {
path[y-1][x] = path[y][x]+1;
}
//이전에 지나왔어야 할 함수가 현재보다 숫자가 크면 현재에서 역행했다고 생각하기.
if((board[y][x-1] == 0) && (path[y][x] < path[y][x-1])) {
path[y][x-1] = path[y][x]+1;
}
}
}
}
public static void initBoard(int array[][], int num){
for(int i=0;i<=n+1;i++){
for(int j =0; j<=m+1; j++){
array[i][j] = num;
}
}
}
}
import java.io.IOException;
public class Main {
public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
public static int[][] board;
public static int[][] path;
public static int ans = 99999;
static int n;
static int m;
static int t;
static int swordx;
static int swordy;
public static void main(String[] args) throws IOException {
String s = br.readLine().trim();
String str1[] = s.split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
t = Integer.parseInt(str1[2]);
path = new int[n+2][m+2];
//경로를 저장할 2차원 배열
initBoard(path, ans);
board = new int[n+2][m+2];
//진짜 판은 미리 1로 감싸기
initBoard(board,1);
for(int i=1;i<n+1;i++){
s = br.readLine().trim();
str1 = s.split(" ");
for(int j=1; j<m+1; j++) {
board[i][j] = Integer.parseInt(str1[j-1]);
//칼 찾을때는 그 좌표만 저장해두고, 0으로 넣기
if(board[i][j] == 2) {
swordx = j;
swordy = i;
board[i][j] = 0;
}
}
}
//n+m보다 t가 작으면 절대 못함.
if(t < n+m-2){
System.out.println("Fail");
return;
}
//findpath를 t번 돌림 (왜냐면 findpath할때 ↑→로 움직여야 할 경우가 발생하면 다시 돌려줘야 하므로.)
for(int a =0; a<t; a++) {
findpath();
}
//칼을 찾았을때랑 비교
if(path[swordy][swordx] < t ) {
path[n][m] = Math.min(path[swordy][swordx] + n-swordy+m-swordx, path[n][m]);
}
//정답 출력하기
if(path[n][m] > t) {
System.out.println("Fail");
}
else {
System.out.println(path[n][m]);
}
}
public static void findpath() {
path[1][1] = 0;
for(int y =1; y < n+1; y++) {
for(int x=1; x<m+1; x++) {
//벽이어도 나가리
if(board[y][x] == 1) continue;
//t보다 커도 나가리
if(path[y][x] > t) continue;
//만약 아래로 한칸 내려간게 현재보다 거리가 멀면
if((board[y+1][x] == 0) && (path[y][x] < path[y+1][x])) {
path[y+1][x] = path[y][x]+1;
}
//마찬가지로 밑으로 내려간게 현재보다 거리가 멀면
if((board[y][x+1] == 0) && (path[y][x] < path[y][x+1])) {
path[y][x+1] = path[y][x]+1;
}
//이전에 지나왔어야 할 함수가 현재보다 숫자가 크면 현재에서 역행했다고 생각하기.
if((board[y-1][x] == 0) && (path[y][x] < path[y-1][x])) {
path[y-1][x] = path[y][x]+1;
}
//이전에 지나왔어야 할 함수가 현재보다 숫자가 크면 현재에서 역행했다고 생각하기.
if((board[y][x-1] == 0) && (path[y][x] < path[y][x-1])) {
path[y][x-1] = path[y][x]+1;
}
}
}
}
public static void initBoard(int array[][], int num){
for(int i=0;i<=n+1;i++){
for(int j =0; j<=m+1; j++){
array[i][j] = num;
}
}
}
}
풀이 (BFS)
일단 X축 , Y축, 이동했는데 걸린 시간을 담을 POINT라는 객체와 이 객체들을 담을 Queue를 만들었다.
방법은 (1,1) 부터 시작해서 전후좌우를 다 탐색해보고 만약에 갈 수 있고(board [] []로 확인),
갔던데가 아니면 (path[] [] 로 확인) 큐에 해당 점을 넣고, 큐가 비어 있을 때 까지 매 점을 탐색하는 것이다.
이때 칼이 저장된 좌표도 매번 물어봐서 따로 탐색한 뒤 정답 비교하기!
코드 (BFS)
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
static int[][] board;
static int[][] path;
static int ans = 99999;
static int n;
static int m;
static int t;
static int swordx;
static int swordy;
//Q에 넣을 좌표와 지금까지 걸린 시간이 담긴 클래스
public static class point{
int x, y, step;
point(int x, int y, int step){
this.x=x;
this.y=y;
this.step =step;
}
}
public static void main(String[] args) throws IOException {
String s = br.readLine().trim();
String str1[] = s.split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
t = Integer.parseInt(str1[2]);
//방문했는지를 저장할 2차원 배열
path = new int[n+2][m+2];
initBoard(path, 0); //방문했으면 1로 바꿔줌
board = new int[n+2][m+2];
//진짜 판은 미리 1로 감싸기
initBoard(board,1);
for(int i=1;i<n+1;i++){
s = br.readLine().trim();
str1 = s.split(" ");
for(int j=1; j<m+1; j++) {
board[i][j] = Integer.parseInt(str1[j-1]);
//칼 찾을때는 그 좌표만 저장해두고, 0으로 넣기
if(board[i][j] == 2) {
swordx = j;
swordy = i;
board[i][j] = 0;
}
}
}
saveQueen(swordx,swordy);
//n+m보다 t가 작으면 절대 못함.
if(t < n+m-2){
System.out.println("Fail");
return;
}
//정답 출력하기
if(ans > t) {
System.out.println("Fail");
}
else {
System.out.println(ans);
}
}
public static void saveQueen(int swordx, int swordy) {
Queue<point> visit= new LinkedList<>();
visit.offer(new point(1,1,0));
while(!visit.isEmpty()) {
point p = visit.poll();
if(p.x == m && p.y == n) {
ans = Math.min(ans, p.step);
return;
}
if(p.x == swordx && p.y == swordy) {
ans = Math.min(ans, p.step + n-swordy+m-swordx);
}
if(board[p.y+1][p.x] == 0 && path[p.y+1][p.x] != 1) {
path[p.y+1][p.x] = 1;
visit.offer(new point(p.x,p.y+1,p.step+1));
}
if(board[p.y][p.x+1] == 0 && path[p.y][p.x+1] != 1) {
path[p.y][p.x+1] = 1;
visit.offer(new point(p.x+1,p.y,p.step+1));
}
if(board[p.y-1][p.x] == 0 && path[p.y-1][p.x] != 1) {
path[p.y-1][p.x] = 1;
visit.offer(new point(p.x,p.y-1,p.step+1));
}
if(board[p.y][p.x-1] == 0 && path[p.y][p.x-1] != 1) {
path[p.y][p.x-1] = 1;
visit.offer(new point(p.x-1,p.y,p.step+1));
}
}
}
public static void initBoard(int array[][], int num){
for(int i=0;i<=n+1;i++){
for(int j =0; j<=m+1; j++){
array[i][j] = num;
}
}
}
}
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
static int[][] board;
static int[][] path;
static int ans = 99999;
static int n;
static int m;
static int t;
static int swordx;
static int swordy;
//Q에 넣을 좌표와 지금까지 걸린 시간이 담긴 클래스
public static class point{
int x, y, step;
point(int x, int y, int step){
this.x=x;
this.y=y;
this.step =step;
}
}
public static void main(String[] args) throws IOException {
String s = br.readLine().trim();
String str1[] = s.split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
t = Integer.parseInt(str1[2]);
//방문했는지를 저장할 2차원 배열
path = new int[n+2][m+2];
initBoard(path, 0); //방문했으면 1로 바꿔줌
board = new int[n+2][m+2];
//진짜 판은 미리 1로 감싸기
initBoard(board,1);
for(int i=1;i<n+1;i++){
s = br.readLine().trim();
str1 = s.split(" ");
for(int j=1; j<m+1; j++) {
board[i][j] = Integer.parseInt(str1[j-1]);
//칼 찾을때는 그 좌표만 저장해두고, 0으로 넣기
if(board[i][j] == 2) {
swordx = j;
swordy = i;
board[i][j] = 0;
}
}
}
saveQueen(swordx,swordy);
//n+m보다 t가 작으면 절대 못함.
if(t < n+m-2){
System.out.println("Fail");
return;
}
//정답 출력하기
if(ans > t) {
System.out.println("Fail");
}
else {
System.out.println(ans);
}
}
public static void saveQueen(int swordx, int swordy) {
Queue<point> visit= new LinkedList<>();
visit.offer(new point(1,1,0));
while(!visit.isEmpty()) {
point p = visit.poll();
if(p.x == m && p.y == n) {
ans = Math.min(ans, p.step);
return;
}
if(p.x == swordx && p.y == swordy) {
ans = Math.min(ans, p.step + n-swordy+m-swordx);
}
if(board[p.y+1][p.x] == 0 && path[p.y+1][p.x] != 1) {
path[p.y+1][p.x] = 1;
visit.offer(new point(p.x,p.y+1,p.step+1));
}
if(board[p.y][p.x+1] == 0 && path[p.y][p.x+1] != 1) {
path[p.y][p.x+1] = 1;
visit.offer(new point(p.x+1,p.y,p.step+1));
}
if(board[p.y-1][p.x] == 0 && path[p.y-1][p.x] != 1) {
path[p.y-1][p.x] = 1;
visit.offer(new point(p.x,p.y-1,p.step+1));
}
if(board[p.y][p.x-1] == 0 && path[p.y][p.x-1] != 1) {
path[p.y][p.x-1] = 1;
visit.offer(new point(p.x-1,p.y,p.step+1));
}
}
}
public static void initBoard(int array[][], int num){
for(int i=0;i<=n+1;i++){
for(int j =0; j<=m+1; j++){
array[i][j] = num;
}
}
}
}
복기
맨 처음에는 재귀함수로 무식하게 다 왔다갔다 해보는 방식으로 해봤다.
하지만 T가 늘어날수록 재귀가 너무 깊어져서 에러가 발생했다.
public static void rescue(int y, int x, int count) {
//만약 끝까지 도달했으면.
if((x == m)&&(y == n)) {
//근데 최소값이면 값 저장.
if(ans > t-count) {
ans = t-count;
}
return;
}
if((n-y+m-x) > count) {
return;
}
//만약에 칼 찾았으면 바로 좌표 계산해서 맨 끝으로 이동.
if((y==swordy)&&(x==swordx)) {
count = count - (n-y + m-x);
rescue(n,m,count);
}
//아래 오른쪽 위 옆으로 재귀 호출
if(board[y][x+1] == 0) {rescue(y,x+1,count-1);}
if(board[y+1][x] == 0) {rescue(y+1,x,count-1);}
if(board[y-1][x] == 0) {rescue(y-1,x,count-1);}
if(board[y][x-1] == 0) {rescue(y,x-1,count-1);}
}그래서 나름 동적 프로그래밍을 생각하면서 2차원 배열에 각 칸마다의 최솟값을 생각하는 방법으로 풀었다.
하지만 채점도중 99퍼에서 자꾸 틀렸는데, 처음에 칸마다 움직임의 최솟값을 정할때 초기화를 9999로 시켰는데, 이를 99999로 바꾸니깐 되었다.
아마 100*100크기의 미로에서 10000번 움직여야 하는 경우 초기화 값이랑 겹쳐서 그런건가 싶기도 한데... 문제에서는 t가 5000 이하라 사실 잘 모르겠다.
시간복잡도는 2중for문을 n번 또 반복하므로 $O(N^3)$ 으로 무식한 방법은 맞는것 같다.
이후에 BFS 탐색을 공부한 뒤, BFS로도 다시 풀어봤다.
확실히 BFS로 $O(N^2)$ 번만 탐색하는게 훨씬 시간적 효율이 있었다.
결과
| 아이디 | 문제 번호 | 결과 | 메모리 | 시간 | 언어 | 코드 길이 | 제출 시간 |
| howtolivelikehuman | 17836 | 맞았습니다!! | 15128KB | 120ms | Java | 2791B | 3달 전 |
| howtolivelikehuman | 17836 | 맞았습니다!! | 15484KB | 692ms | Java | 3014B | 3달 전 |
"originWidth":1134,"originHeight":1134,"style":"alignCenter","mobileStyle":"widthContent","width":300,"filename":"블로그 사진.jpg"}_##]
문제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
| 1초 | 256 MB | 2373 | 545 | 412 | 21.950% |
용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.
마왕은 용사가 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈를 반드시 하고 싶은 용사는 T시간 내에 반드시 공주님이 있는 곳으로 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸리며, 공주님이 있는 곳에 정확히 T초만에 도달하는 경우도, 구출 할 수 있다.
성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.
우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.
입력
첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 5000)
두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.
출력
용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.
만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "`Fail`"을 출력한다.
풀이 (DP)
path라는 배열을 만들어, board(미로) 에서 매 칸마다의 최소 움직임을 저장해둔다.
2중for문으로 미로의 처음부터 끝까지 돌린다.
이때 역순으로 움직여야 할 상황이 발생하므로, 이 이중for문을 t번 반복한다.
마지막에 칼을 찾았을 때의 경로랑 비교해서 정답 출력
코드 (DP)
import java.io.IOException;
public class Main {
public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
public static int[][] board;
public static int[][] path;
public static int ans = 99999;
static int n;
static int m;
static int t;
static int swordx;
static int swordy;
public static void main(String[] args) throws IOException {
String s = br.readLine().trim();
String str1[] = s.split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
t = Integer.parseInt(str1[2]);
path = new int[n+2][m+2];
//경로를 저장할 2차원 배열
initBoard(path, ans);
board = new int[n+2][m+2];
//진짜 판은 미리 1로 감싸기
initBoard(board,1);
for(int i=1;i<n+1;i++){
s = br.readLine().trim();
str1 = s.split(" ");
for(int j=1; j<m+1; j++) {
board[i][j] = Integer.parseInt(str1[j-1]);
//칼 찾을때는 그 좌표만 저장해두고, 0으로 넣기
if(board[i][j] == 2) {
swordx = j;
swordy = i;
board[i][j] = 0;
}
}
}
//n+m보다 t가 작으면 절대 못함.
if(t < n+m-2){
System.out.println("Fail");
return;
}
//findpath를 t번 돌림 (왜냐면 findpath할때 ↑→로 움직여야 할 경우가 발생하면 다시 돌려줘야 하므로.)
for(int a =0; a<t; a++) {
findpath();
}
//칼을 찾았을때랑 비교
if(path[swordy][swordx] < t ) {
path[n][m] = Math.min(path[swordy][swordx] + n-swordy+m-swordx, path[n][m]);
}
//정답 출력하기
if(path[n][m] > t) {
System.out.println("Fail");
}
else {
System.out.println(path[n][m]);
}
}
public static void findpath() {
path[1][1] = 0;
for(int y =1; y < n+1; y++) {
for(int x=1; x<m+1; x++) {
//벽이어도 나가리
if(board[y][x] == 1) continue;
//t보다 커도 나가리
if(path[y][x] > t) continue;
//만약 아래로 한칸 내려간게 현재보다 거리가 멀면
if((board[y+1][x] == 0) && (path[y][x] < path[y+1][x])) {
path[y+1][x] = path[y][x]+1;
}
//마찬가지로 밑으로 내려간게 현재보다 거리가 멀면
if((board[y][x+1] == 0) && (path[y][x] < path[y][x+1])) {
path[y][x+1] = path[y][x]+1;
}
//이전에 지나왔어야 할 함수가 현재보다 숫자가 크면 현재에서 역행했다고 생각하기.
if((board[y-1][x] == 0) && (path[y][x] < path[y-1][x])) {
path[y-1][x] = path[y][x]+1;
}
//이전에 지나왔어야 할 함수가 현재보다 숫자가 크면 현재에서 역행했다고 생각하기.
if((board[y][x-1] == 0) && (path[y][x] < path[y][x-1])) {
path[y][x-1] = path[y][x]+1;
}
}
}
}
public static void initBoard(int array[][], int num){
for(int i=0;i<=n+1;i++){
for(int j =0; j<=m+1; j++){
array[i][j] = num;
}
}
}
}
풀이 (BFS)
일단 X축 , Y축, 이동했는데 걸린 시간을 담을 POINT라는 객체와 이 객체들을 담을 Queue를 만들었다.
방법은 (1,1) 부터 시작해서 전후좌우를 다 탐색해보고 만약에 갈 수 있고(board [] []로 확인),
갔던데가 아니면 (path[] [] 로 확인) 큐에 해당 점을 넣고, 큐가 비어 있을 때 까지 매 점을 탐색하는 것이다.
이때 칼이 저장된 좌표도 매번 물어봐서 따로 탐색한 뒤 정답 비교하기!
코드 (BFS)
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
static int[][] board;
static int[][] path;
static int ans = 99999;
static int n;
static int m;
static int t;
static int swordx;
static int swordy;
//Q에 넣을 좌표와 지금까지 걸린 시간이 담긴 클래스
public static class point{
int x, y, step;
point(int x, int y, int step){
this.x=x;
this.y=y;
this.step =step;
}
}
public static void main(String[] args) throws IOException {
String s = br.readLine().trim();
String str1[] = s.split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
t = Integer.parseInt(str1[2]);
//방문했는지를 저장할 2차원 배열
path = new int[n+2][m+2];
initBoard(path, 0); //방문했으면 1로 바꿔줌
board = new int[n+2][m+2];
//진짜 판은 미리 1로 감싸기
initBoard(board,1);
for(int i=1;i<n+1;i++){
s = br.readLine().trim();
str1 = s.split(" ");
for(int j=1; j<m+1; j++) {
board[i][j] = Integer.parseInt(str1[j-1]);
//칼 찾을때는 그 좌표만 저장해두고, 0으로 넣기
if(board[i][j] == 2) {
swordx = j;
swordy = i;
board[i][j] = 0;
}
}
}
saveQueen(swordx,swordy);
//n+m보다 t가 작으면 절대 못함.
if(t < n+m-2){
System.out.println("Fail");
return;
}
//정답 출력하기
if(ans > t) {
System.out.println("Fail");
}
else {
System.out.println(ans);
}
}
public static void saveQueen(int swordx, int swordy) {
Queue<point> visit= new LinkedList<>();
visit.offer(new point(1,1,0));
while(!visit.isEmpty()) {
point p = visit.poll();
if(p.x == m && p.y == n) {
ans = Math.min(ans, p.step);
return;
}
if(p.x == swordx && p.y == swordy) {
ans = Math.min(ans, p.step + n-swordy+m-swordx);
}
if(board[p.y+1][p.x] == 0 && path[p.y+1][p.x] != 1) {
path[p.y+1][p.x] = 1;
visit.offer(new point(p.x,p.y+1,p.step+1));
}
if(board[p.y][p.x+1] == 0 && path[p.y][p.x+1] != 1) {
path[p.y][p.x+1] = 1;
visit.offer(new point(p.x+1,p.y,p.step+1));
}
if(board[p.y-1][p.x] == 0 && path[p.y-1][p.x] != 1) {
path[p.y-1][p.x] = 1;
visit.offer(new point(p.x,p.y-1,p.step+1));
}
if(board[p.y][p.x-1] == 0 && path[p.y][p.x-1] != 1) {
path[p.y][p.x-1] = 1;
visit.offer(new point(p.x-1,p.y,p.step+1));
}
}
}
public static void initBoard(int array[][], int num){
for(int i=0;i<=n+1;i++){
for(int j =0; j<=m+1; j++){
array[i][j] = num;
}
}
}
}
복기
맨 처음에는 재귀함수로 무식하게 다 왔다갔다 해보는 방식으로 해봤다.
하지만 T가 늘어날수록 재귀가 너무 깊어져서 에러가 발생했다.
public static void rescue(int y, int x, int count) {
//만약 끝까지 도달했으면.
if((x == m)&&(y == n)) {
//근데 최소값이면 값 저장.
if(ans > t-count) {
ans = t-count;
}
return;
}
if((n-y+m-x) > count) {
return;
}
//만약에 칼 찾았으면 바로 좌표 계산해서 맨 끝으로 이동.
if((y==swordy)&&(x==swordx)) {
count = count - (n-y + m-x);
rescue(n,m,count);
}
//아래 오른쪽 위 옆으로 재귀 호출
if(board[y][x+1] == 0) {rescue(y,x+1,count-1);}
if(board[y+1][x] == 0) {rescue(y+1,x,count-1);}
if(board[y-1][x] == 0) {rescue(y-1,x,count-1);}
if(board[y][x-1] == 0) {rescue(y,x-1,count-1);}
}그래서 나름 동적 프로그래밍을 생각하면서 2차원 배열에 각 칸마다의 최솟값을 생각하는 방법으로 풀었다.
하지만 채점도중 99퍼에서 자꾸 틀렸는데, 처음에 칸마다 움직임의 최솟값을 정할때 초기화를 9999로 시켰는데, 이를 99999로 바꾸니깐 되었다.
아마 100*100크기의 미로에서 10000번 움직여야 하는 경우 초기화 값이랑 겹쳐서 그런건가 싶기도 한데... 문제에서는 t가 5000 이하라 사실 잘 모르겠다.
시간복잡도는 2중for문을 n번 또 반복하므로 $O(N^3)$ 으로 무식한 방법은 맞는것 같다.
이후에 BFS 탐색을 공부한 뒤, BFS로도 다시 풀어봤다.
확실히 BFS로 $O(N^2)$ 번만 탐색하는게 훨씬 시간적 효율이 있었다.
결과
| 아이디 | 문제 번호 | 결과 | 메모리 | 시간 | 언어 | 코드 길이 | 제출 시간 |
| howtolivelikehuman | 17836 | 맞았습니다!! | 15128KB | 120ms | Java | 2791B | 3달 전 |
| howtolivelikehuman | 17836 | 맞았습니다!! | 15484KB | 692ms | Java | 3014B | 3달 전 |
'알고리즘 > 문제풀이' 카테고리의 다른 글
| 스티커 붙이기 (백준 18808) [JAVA] (0) | 2020.07.23 |
|---|---|
| 탑 (프로그래머스) [JAVA] (0) | 2020.07.21 |
| 달팽이 리스트 (백준 17827번) [JAVA] (0) | 2020.07.11 |
| 제곱수의 합 (백준 1699번) [JAVA] (0) | 2020.07.10 |
| 종이의 개수 (백준 1780번) (0) | 2020.07.09 |
Comment