어제 못풀었던 문제를 푸려고 시도하다가, 못풀겠어가지고 다른 문제를 풀었음
치욕적임
내일은 꼭 풀어내겠음...
https://www.codetree.ai/missions/2/problems/escape-with-min-distance/introduction
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
난이도
- 하
실수한 점 & 배운 점
- 최단거리를 구하기 위한 step 2차원 배열에 대해 각 거리를 계산하는 부분을 잘못 설정함.
같은 크기의 step을 매겨줘야 하는 깊이에 대해서 1씩 증가하게 매겨지도록 로직을 짜놔서 12가 나와야하는데 14가 나오는 등 step이 엉망으로 세어졌음
import java.util.*;
import java.io.*;
class Vertex{
int r;
int c;
public Vertex(int r, int c){
this.r = r;
this.c = c;
}
}
public class Main {
static int[] dr = {1, 0, -1, 0};
static int[] dc = {0, 1, 0, -1};
static int n;
static int m;
static int[][] grid;
static boolean[][] isVisited;
static int[][] step;
static int currNum = 0;
static int answer = -1;
static Queue<Vertex> queue;
public static void findWay(int r, int c){
while(!queue.isEmpty()){
Vertex curr = queue.poll();
currNum = step[curr.r][curr.c];
for(int i = 0; i<4; i++){
int new_r = curr.r + dr[i];
int new_c = curr.c + dc[i];
if(canGo(new_r, new_c)){
isVisited[new_r][new_c] = true;
step[new_r][new_c] = currNum+1;
queue.add(new Vertex(new_r, new_c));
}
}
}
}
public static boolean isRange(int r, int c){
return (r>=0 && r<n && c>=0 && c<m);
}
public static boolean canGo(int r, int c){
if(!isRange(r, c)) return false;
if(grid[r][c]==0 || isVisited[r][c]) return false;
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
grid = new int[n][m];
isVisited = new boolean[n][m];
step = new int[n][m];
queue = new LinkedList<>();
for(int i = 0; i<n; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j<m; j++){
grid[i][j] = Integer.parseInt(st.nextToken());
}
}
isVisited[0][0] = true;
queue.add(new Vertex(0, 0));
findWay(0, 0);
if(isVisited[n-1][m-1]) answer = step[n-1][m-1];
System.out.println(answer);
}
}
'코딩테스트 > 매일 한 문제' 카테고리의 다른 글
[2024.11.08]가중치가 동일한 그래프에서의 BFS / 나이트 (1) | 2024.11.09 |
---|---|
[2024.11.06] BFS 탐색 / 우리는하나 (2) | 2024.11.06 |
[2024.11.05] BFS 탐색 / 빙하 (7) | 2024.11.05 |
[2024.11.04] BFS 탐색 / 돌 잘 치우기 (2) | 2024.11.04 |
[2024.11.04] BFS 탐색 / K번 최댓값으로 이동하기 (0) | 2024.11.04 |
댓글