728x90
728x90
오늘의 문제는 보급로이다.
처음엔 무조건 완전탐색!
이 문제를 보고 BFS를 사용해야겠다는 생각을 했다.
하지만 단지 방문처리조건 하나만으로 목적지 도착시 값이 최소로 걸린 시간이라 보장할 수 있을까?
결론은 아니다. 문제에 제시된 예시만 확인해도 아닌 경우가 많다는 것을 알 수 있다.
그렇다면 어떤 방법을 통해서 이를 해결할 수 있을까?
나는 좌표마다 방문처리와 현재까지의 최소 시간을 저장해 비교하는 방법으로 해결했다.
코드는 다음과 같다.
( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘보여요 ! )
( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )
import java.util.*;
import java.io.*;
public class Solution {
//문제에서 주어지는 테스트케이스마다 주어지는 N과 정보를 받을 map
//그리고 방문처리를 위한 visited, 최소 시간을 확인할 cost 배열을 선언해준다.
static int N, map[][], visited[][], cost[][];
//사방탐색을 위한 dr과 dc 배열도 선언해준다 ~
static int [] dr = {-1, 0, 1, 0};
static int [] dc = {0, 1, 0, -1};
public static void main(String [] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
String str;
for(int tc = 1; tc<=T; tc++){
sb.append("#").append(tc).append(" ");
N = Integer.parseInt(br.readLine());
map = new int [N][N];
visited = new int [N][N];
cost = new int [N][N];
for(int i = 0; i<N; i++){
str = br.readLine();
for(int j = 0; j<N; j++){
map[i][j] = str.charAt(j) - '0';
}
}
//각 테스트케이스의 입력을 마치고 bfs()함수를 실행해 준다. 36번줄로.
bfs();
sb.append(cost[N-1][N-1]).append("\n");
}
System.out.print(sb);
}
private static void bfs(){
//제네릭을 int배열로 설정한 큐를 선언해준다.
Queue<int []> q = new LinkedList<>();
q.offer(new int [] {0, 0, 0}); // 배열의 [0]과[1]은 r과c의좌표, [2]는 해당좌표의 최소시간이다.
visited[0][0] = 1; //시작점은 방문처리를 해주고 !
int [] temp;
while(!q.isEmpty()){
temp = q.poll();
//만약 지금 나의 해당 좌표 최소시간이 최소가 아니라면?continue;
//이 경우는 나와 다른 루트로 해당 좌표를 거치며, 그 시간이 나보다 적을 때이다.
//현재 내가 온 루트는 최소가 아니므로 고려대상에서 제외되는 부분이다.
if(temp[2] > cost[temp[0]][temp[1]]) continue;
int nr, nc, ifCost; // 차례로 다음r좌표, 다음c좌표, 이 루트를 통해 해당좌표로 간다면 소요시간이다.
for(int i = 0; i<4; i++){ //사방탐색을 위한 반복문 !
nr = temp[0] + dr[i];
nc = temp[1] + dc[i];
//만약 좌표가 범위를 벗어난다면 continue;
if(nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
//현재 나의 소요시간과 해당 좌표를 거칠시 소요시간을 더한 값 !
ifCost = temp[2] + map[nr][nc];
//만약 방문한적 없다면 해당좌표에 예상 소요시간을 대입하고
//방문처리해주고 큐에 넣어준다 ~
if(visited[nr][nc] == 0){
cost[nr][nc] = ifCost;
visited[nr][nc] = 1;
q.offer(new int [] {nr, nc, ifCost});
//아니라면?
//그리고 이전에 방문했을 때의 소요시간보다 현재 내 예상소요시간이 더 낮다면?
//예상 소요시간을 업데이트해주고 큐에 넣어준다 ~
}else{
if(cost[nr][nc] > ifCost){
cost[nr][nc] = ifCost;
q.offer(new int [] {nr, nc, ifCost});
}
}
}
}
}
}
bfs문제를 오랜만에 풀었지만 우려와 달리 잘 풀어낸 모습..ㅎ (뿌듯)
궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~
728x90