-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
잃어버린 강아지 질문드립니다.
23.06.10 21:37 작성 조회수 187
0
초기에 현수 위치와 강아지 위치를 큐에 넣어주고 탐색했는데, 큐에 넣고 탐색하면 안되는건가요???
import java.io.*;
import java.util.*;
class Node {
int x;
int y;
Node(int x,int y){
this.x=x;
this.y=y;
}
}
public class Main {
public int solution(int[][] board){
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
int n =board.length;
int m=board[0].length;
int d1=0, d2=0;
Queue<Node> huyn = new LinkedList<>();
Queue<Node> dog = new LinkedList<>();
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(board[i][j]==2) {
huyn.add(new Node(i,j));
}
if(board[i][j]==3) {
dog.add(new Node(i,j));
}
}
}
int time=0;
while(time<10000) {
time++;
boolean flag1=true, flag2=true;
Node ddog = dog.poll();
Node h = huyn.poll();
int nxh = h.x+dx[d1]; //현수의 다음 노드
int nyh = h.y+dy[d1];
int dogx = ddog.x+dx[d2];
int dogy = ddog.y+dy[d2];
if(nxh<0 || nyh<0 || nxh>=n || nyh>=m || board[nxh][nyh]==1) {
d1 = (d1+1)%4;
flag1 = false;
}
if(dogx<0 || dogy<0 || dogx>=n || dogy>=m || board[dogx][dogy]==1) {
d2 = (d2+1)%4;
flag2 = false;
}
if(flag1) {
huyn.add(new Node(nxh,nyh));
}
if(flag2) {
dog.add(new Node(dogx, dogy));
}
if(nxh==dogx && nyh==dogy) {
return time;
}
}
return 0;
}
public static void main(String[] args){
Main T = new Main();
int[][] arr1 = {
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 2, 0, 0},
{1, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 3, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 1, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 0, 0, 0, 0, 0}
};
System.out.println(T.solution(arr1));
int[][] arr2 = {
{1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 1, 1, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 2, 1},
{0, 0, 0, 1, 0, 1, 0, 0, 0, 1},
{0, 1, 0, 1, 0, 0, 0, 0, 0, 3}
};
System.out.println(T.solution(arr2));
}
}
답변을 작성해보세요.
0
0
김태원
지식공유자2023.06.11
안녕하세요^^
할 수는 있겠지만 큐로는 효율성이 좋지 않습니다. 영상의 방법을 추천합니다.
현수만 생각해 보죠.
현수가 출발지에서 북쪽으로 이동하려고 하는데 바로 위쪽에 나무를 만났다면 출발 위치에서 시계방향으로 회전만 해야 합니다. 그러면 큐에 꺼냈던 출발지 좌표를 다시 큐에 넣어주어야 다음 단계에서 출발지에서 3시 방향으로 갈 수 있는지 확인할 수 있습니다. 다시 넣어 주시 않으면 큐는 비어있는데 poll()로 꺼내겠다는 실행을 해 널포인트 에러가 나는 것입니다.
또한 if(nxh==dogx && nyh==dogy) 와 같이 비교를 하는데 [nxh, nyh]는 현재 현수의 위치가 아닐 수도 있습니다. 만약 현수가 회전을 했을 경우 [nxh, nyh]로 가지 않았으므로 현수의 현재 위치가 아닙니다. 강아지도 마찬가지 입니다. 현수나 강아지의 현재 위치는 큐에 있는 좌표입니다.
아래는 에러 수정을 한 코드입니다.
public int solution(int[][] board){
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
int n =board.length;
int m=board[0].length;
int d1=0, d2=0;
Queue<Node> huyn = new LinkedList<>();
Queue<Node> dog = new LinkedList<>();
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(board[i][j]==2) {
huyn.add(new Node(i,j));
}
if(board[i][j]==3) {
dog.add(new Node(i,j));
}
}
}
int time=0;
while(time<10000) {
time++;
boolean flag1=true, flag2=true;
Node ddog = dog.poll();
Node h = huyn.poll();
int nxh = h.x+dx[d1]; //현수의 다음 노드
int nyh = h.y+dy[d1];
int dogx = ddog.x+dx[d2];
int dogy = ddog.y+dy[d2];
if(nxh<0 || nyh<0 || nxh>=n || nyh>=m || board[nxh][nyh]==1) {
d1 = (d1+1)%4;
huyn.add(new Node(h.x,h.y));
flag1 = false;
}
if(dogx<0 || dogy<0 || dogx>=n || dogy>=m || board[dogx][dogy]==1) {
d2 = (d2+1)%4;
dog.add(new Node(ddog.x, ddog.y));
flag2 = false;
}
if(flag1) {
huyn.add(new Node(nxh,nyh));
}
if(flag2) {
dog.add(new Node(dogx, dogy));
}
if(huyn.peek().x==dog.peek().x && huyn.peek().y==dog.peek().y) {
return time;
}
}
return 0;
}
답변 2