728x90
| 코딩 테스트 풀이 체크리스트 |
|
| 2시간 내에 풀었는가? | O |
| 본인의 실력으로 풀었는가? | O |
코딩테스트 연습 - 게임 맵 최단거리
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1
programmers.co.kr
import java.util.*;
class Solution {
public int solution(int[][] maps) {
int row = maps.length;
int col = maps[0].length;
boolean[][] check = new boolean[row][col]; //다녀왔는지 체크용
//BFS를 구현하기 위한 큐
Queue<Point> q = new LinkedList<>();
q.add(new Point(0, 0, 1));
//상하좌우 움직일 배열
int[] xMove = {1, -1, 0, 0};
int[] yMove = {0, 0, -1, 1};
while (!q.isEmpty()) {
Point p = q.poll();
int x = p.x;
int y = p.y;
int num = p.num;
//만약 x, y가 상대팀 진영이라면 num 리턴하기
if (x == row - 1 && y == col - 1) return num;
for (int i = 0; i < 4; i++) {
int xm = x + xMove[i];
int ym = y + yMove[i];
//움직일 좌표가 범위를 넘진 않았는지, 이미 방문한 좌표인지, 해당 좌표가 벽인지 파악
if (xm < 0 || ym < 0 || xm >= row || ym >= col) continue;
if (check[xm][ym] || maps[xm][ym] == 0) continue;
//방문 체크하고 q에 추가하기
check[xm][ym] = true;
q.add(new Point(xm, ym, num+1));
}
}
//while문을 통과했는데도 리턴되지 않았다면 그냥 -1 리턴
return -1;
}
}
class Point {
int x, y, num;
public Point(int x, int y, int num) {
this.x = x;
this.y = y;
this.num = num;
}
}
정확성 테스트
| 테스트 1 〉 | 통과 (0.31ms, 78.5MB) |
| 테스트 2 〉 | 통과 (0.26ms, 77.7MB) |
| 테스트 3 〉 | 통과 (0.32ms, 78.9MB) |
| 테스트 4 〉 | 통과 (0.29ms, 73.9MB) |
| 테스트 5 〉 | 통과 (0.30ms, 67.5MB) |
| 테스트 6 〉 | 통과 (0.29ms, 76.5MB) |
| 테스트 7 〉 | 통과 (0.37ms, 79.4MB) |
| 테스트 8 〉 | 통과 (0.29ms, 71.7MB) |
| 테스트 9 〉 | 통과 (0.38ms, 86.7MB) |
| 테스트 10 〉 | 통과 (0.44ms, 67.1MB) |
| 테스트 11 〉 | 통과 (0.30ms, 77.6MB) |
| 테스트 12 〉 | 통과 (0.31ms, 73.1MB) |
| 테스트 13 〉 | 통과 (0.44ms, 75.5MB) |
| 테스트 14 〉 | 통과 (0.40ms, 77.4MB) |
| 테스트 15 〉 | 통과 (0.28ms, 71.2MB) |
| 테스트 16 〉 | 통과 (0.39ms, 76.8MB) |
| 테스트 17 〉 | 통과 (0.41ms, 78.7MB) |
| 테스트 18 〉 | 통과 (0.26ms, 71.7MB) |
| 테스트 19 〉 | 통과 (0.36ms, 73.6MB) |
| 테스트 20 〉 | 통과 (0.32ms, 68.5MB) |
| 테스트 21 〉 | 통과 (0.26ms, 75.3MB) |
효율성 테스트
| 테스트 1 〉 | 통과 (10.62ms, 52.9MB) |
| 테스트 2 〉 | 통과 (3.84ms, 54.3MB) |
| 테스트 3 〉 | 통과 (9.10ms, 56MB) |
| 테스트 4 〉 | 통과 (4.86ms, 56.2MB) |
DFS로 풀면 효율성 테스트에서 시간초과가 나오고, BFS로 풀어야 통과함
728x90
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
| [Java] 프로그래머스 - 다단계 칫솔 판매 (3단계) (0) | 2022.06.07 |
|---|---|
| [Java] 프로그래머스 - 예상 대진표 (2단계) (0) | 2022.06.03 |
| [Java] 프로그래머스 - 네트워크 (3단계) (0) | 2022.05.27 |
| [Java] 프로그래머스 - 정수 삼각형 (3단계) (0) | 2022.05.26 |
| [Java] 프로그래머스 - 조이스틱 (2단계) (0) | 2022.05.25 |
