코딩테스트 - 프로그래머스/JAVA
[프로그래머스 / 깊이/너비 우선 탐색(DFS/BFS) / 자바(JAVA)] 게임 맵 최단거리
읁;
2024. 5. 19. 21:47
[프로그래머스 / 깊이/너비 우선 탐색(DFS/BFS) / 자바(JAVA)] 게임 맵 최단거리
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[ 요약 ]
더보기
더보기
시작 시간 : PM 7:07
종료 시간 : PM 8:45
소요 시간(분) : 98분
도전 횟수 (제출 횟수) : 4
로직 및 풀이 참고 여부 : O
https://velog.io/@minji0801/오답노트파이썬-프로그래머스-게임-맵-최단거리
[ 풀어보기 ]
정답 풀이
📌 로직
- BFS(너비 우선 탐색). Queue를 이용해서 구현할 수 있다.
- 시작 노드를 Queue에 넣는다.
- Queue에서 노드를 꺼내고, 인접 노드 중 방문하지 않은 노드를 Queue에 넣는다.
- 2번 과정을 Queue에 노드가 없을 때까지 반복한다.
📌 코드
import java.util.*;
class Solution {
int[][] maps;
int n = 0;
int m = 0;
public int solution(int[][] maps) {
n = maps.length;
m = maps[0].length;
this.maps = maps;
int answer = bfs(0,0);
return (answer == 1) ? -1 : answer;
// answer이 1이면 방문할 수 없다는 뜻 => -1을 return 한다.
}
private int bfs(int x, int y) {
// 상, 하, 좌, 우를 살펴주기 위한 배열
int[] dx = {-1, 1, 0, 0}; // 행 이동
int[] dy = {0, 0, -1, 1}; // 열 이동
Queue q = new LinkedList();
// Queue에는 현재 방문한 좌표로부터
// 인접한 노드들 중, 방문하지 않은 노드를 넣어줄 것.
int[] a = {x, y}; // 시작점
q.add(a); // Queue에 넣어준다.
while(!q.isEmpty()) {
int[] b = (int[])q.poll(); // 노드를 꺼내준다.
x = b[0];
y = b[1];
for(int i=0; i<4; i++) { // 상하좌우를 살펴준다.
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 범위 벗어남
else if(maps[nx][ny] == 0) continue; // 벽임
else if(maps[nx][ny] == 1) { // 인접 노드가 방문하지 않은 노드라면
int[] c = {nx, ny};
q.add(c); // Queue에 넣어준다.
maps[nx][ny] = maps[x][y] + 1;
// 시작 좌표부터 (nx, ny) 까지 이동한 칸 수를
// 점점 누적해서 더해준다.
// ( 방문 여부 체크가 되기도 한다. )
}
}
}
return maps[n-1][m-1];
}
}📌 채점 결과
정확성 테스트
테스트 1 〉 통과 (0.15ms, 81.5MB)
테스트 2 〉 통과 (0.17ms, 77.1MB)
테스트 3 〉 통과 (0.15ms, 72MB)
테스트 4 〉 통과 (0.20ms, 74.2MB)
테스트 5 〉 통과 (0.19ms, 67.4MB)
테스트 6 〉 통과 (0.17ms, 67.1MB)
테스트 7 〉 통과 (0.20ms, 67.6MB)
테스트 8 〉 통과 (0.15ms, 72.3MB)
테스트 9 〉 통과 (0.19ms, 72.5MB)
테스트 10 〉 통과 (0.21ms, 75.3MB)
테스트 11 〉 통과 (0.14ms, 72.7MB)
테스트 12 〉 통과 (0.19ms, 67MB)
테스트 13 〉 통과 (0.19ms, 80.5MB)
테스트 14 〉 통과 (0.21ms, 74.8MB)
테스트 15 〉 통과 (0.14ms, 75.5MB)
테스트 16 〉 통과 (0.16ms, 66.9MB)
테스트 17 〉 통과 (0.19ms, 76.3MB)
테스트 18 〉 통과 (0.19ms, 92.3MB)
테스트 19 〉 통과 (0.17ms, 67.2MB)
테스트 20 〉 통과 (0.17ms, 76.3MB)
테스트 21 〉 통과 (0.16ms, 83.1MB)
효율성 테스트
테스트 1 〉 통과 (8.67ms, 52.6MB)
테스트 2 〉 통과 (3.30ms, 54.1MB)
테스트 3 〉 통과 (5.21ms, 52.7MB)
테스트 4 〉 통과 (4.20ms, 52.5MB)
채점 결과
정확성: 69.9
효율성: 30.1
합계: 100.0 / 100.0[코드 개선]
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
else if(maps[nx][ny] == 0) continue;
// maps[nx][ny]가 1이 아닌 경우 모두
// 방문할 필요가 없는 노드이므로,
// maps[nx][ny]가 0인 경우의 if문을 따로 만들어주지 않아도 될 듯하다.
else if(maps[nx][ny] == 1) {
int[] c = {nx, ny};
q.add(c); // Queue에 넣어준다.
maps[nx][ny] = maps[x][y] + 1;
}
}
📌코드
import java.util.*;
class Solution {
int[][] maps;
int n = 0;
int m = 0;
public int solution(int[][] maps) {
n = maps.length;
m = maps[0].length;
this.maps = maps;
int answer = bfs(0,0);
return (answer == 1) ? -1 : answer;
// answer이 1이면 방문할 수 없다는 뜻 => -1을 return 한다.
}
private int bfs(int x, int y) {
// 상, 하, 좌, 우를 살펴주기 위한 배열
int[] dx = {-1, 1, 0, 0}; // 행 이동
int[] dy = {0, 0, -1, 1}; // 열 이동
Queue q = new LinkedList();
// Queue에는 현재 방문한 좌표로부터
// 인접한 노드들 중, 방문하지 않은 노드를 넣어줄 것.
int[] a = {x, y}; // 시작점
q.add(a); // Queue에 넣어준다.
while(!q.isEmpty()) {
int[] b = (int[])q.poll(); // 노드를 꺼내준다.
x = b[0];
y = b[1];
for(int i=0; i<4; i++) { // 상하좌우를 살펴준다.
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 범위 벗어남
// else if(maps[nx][ny] == 0) continue;
else if(maps[nx][ny] == 1) { // 인접 노드가 방문하지 않은 노드라면
int[] c = {nx, ny};
q.add(c); // Queue에 넣어준다.
maps[nx][ny] = maps[x][y] + 1;
// 시작 좌표부터 (nx, ny) 까지 이동한 칸 수를
// 점점 누적해서 더해준다.
// ( 방문 여부 체크가 되기도 한다. )
}
}
}
return maps[n-1][m-1];
}
}📌 채점 결과
정확성 테스트
테스트 1 〉 통과 (0.18ms, 72MB)
테스트 2 〉 통과 (0.13ms, 77.5MB)
테스트 3 〉 통과 (0.20ms, 73.1MB)
테스트 4 〉 통과 (0.11ms, 70.7MB)
테스트 5 〉 통과 (0.14ms, 72.2MB)
테스트 6 〉 통과 (0.19ms, 74.9MB)
테스트 7 〉 통과 (0.17ms, 75.4MB)
테스트 8 〉 통과 (0.25ms, 74.4MB)
테스트 9 〉 통과 (0.18ms, 74MB)
테스트 10 〉 통과 (0.15ms, 75.1MB)
테스트 11 〉 통과 (0.22ms, 74.6MB)
테스트 12 〉 통과 (0.17ms, 74.6MB)
테스트 13 〉 통과 (0.21ms, 77.6MB)
테스트 14 〉 통과 (0.13ms, 75.5MB)
테스트 15 〉 통과 (0.18ms, 76.6MB)
테스트 16 〉 통과 (0.12ms, 75.5MB)
테스트 17 〉 통과 (0.21ms, 74.9MB)
테스트 18 〉 통과 (0.11ms, 75.4MB)
테스트 19 〉 통과 (0.12ms, 74MB)
테스트 20 〉 통과 (0.12ms, 76.6MB)
테스트 21 〉 통과 (0.12ms, 76.8MB)
효율성 테스트
테스트 1 〉 통과 (8.92ms, 53.8MB)
테스트 2 〉 통과 (2.45ms, 54MB)
테스트 3 〉 통과 (5.75ms, 56.3MB)
테스트 4 〉 통과 (3.79ms, 53.1MB)
채점 결과
정확성: 69.9
효율성: 30.1
합계: 100.0 / 100.0
큰... 차이는 없는 듯? 큼큼.
[배운 점]
📌 배운 것
- BFS(넓이 우선 탐색) 를 구현하는 방법
- Queue를 이용해서 구현할 수 있다.
- 이해가 안 가서 직접 손으로 작동 과정을 하나하나 그려봤더니 이해가 갔다.