[Unsolved][JAVA] SWEA 1249 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

 

1. 서론

 

정말... 이 문제를 풀기까지 여러 문제가 많았다^^,,, 하지만 차마 여기에 적진 않겠다. 

(대충 BFS, DFS, 백트래킹, 에러 관련 얘기들)

 

2. 문제 풀이

 

2차원 배열이 주어진다. 이 배열의 0, 0에서 시작해서 n - 1, n - 1 칸에 도착할 때까지 가장 최소의 배열합을 구하는 문제다. 

 

풀이 방법은 풀기 나름이겠지만 나는 처음에 백트래킹이라고 생각했다. 그런데 종료 조건을 딱히 세울 수 없어서 메모하는 형식으로(배열에 경로마다 지나가는 동안 값을 저장. 이 방법을 칭하는 무슨 말이 있는데.... DP인가 메모인가... 모르겠다 아마 메모이제이션...) 예전에 풀었던 '미로 탐색' 문제와 비슷했기 때문에 그렇게 풀려고 했다. 그런데... 나름대로 구현했지만 결국 풀지 못하고 답답해서 구글링을 갈겼다...

 

미로 탐색 문제

https://coding-log.tistory.com/144

[Unsolved][C++] 백준 2178 미로 탐색

 

참고한 블로그

https://codingtalk.tistory.com/67

SWEA_1249 보급로(자바) / BFS

 

 

 

 

 

사실 굉장히 여러 블로그를 봤고 따라도 해보고 참고도 해봤지만 이 블로그가 제일 내가 생각한 아이디어와 흡사했다.

이 블로그를 보고 좀 슬펐다... 거의 다 생각했는데 그걸 구현하지 못해서...

 

BFS로 풀면서  메모를 활용하는 방식이다.

포인트는 이동하면서 메모에 이동경로별로 값을 저장하는데 경로별로 도착했을 때 가장 최솟값을 남겨서 저장해주는 것이다. 뿐만 아니라 큐를 돌면서도 방문했는지 혹은 지금 가려는 경로가 이미 갔던 경로보다 값이 작은 지를 판별하고 그 조건에 맞으면 값을 저장하는 식이다.

 

나의 실수는 무조건 방문한 곳은 안 가려고 했다는 것(근데 이렇게 하면 최소 경로를 찾을 수 없음)

그리고 원래의 값과 새로운 경로의 값을 비교하고 값을 저장하지 않은 것(이렇게 안하면 최소 경로를 찾을 수 없음)

결국... 아무 것도 몰랐다는 뜻이잖아?^^

 

아 그리고 코드 제출할 때도 클래스 이름이 Solution이어야만 돌아가는 걸 알았기 때문에 이클립스에서 클래스 이름을 'solution'이라고 제출하고 잘 돌길래 복붙 해서 냈더니

 

Memory error occured, (e.g. segmentation error, memory limit Exceed, stack overflow,... etc)

 

이 에러가 났다... 난 돌 뻔했다. 이클립스에서는 너무나 잘 돌았기 때문에.

Solution을 solution이라고 적었다고 이 에러를 뱉어낸 것이다... (이것 때문인지 깨닫는데 오래 걸림)

SWEA에서 문제푸는 사람들 주의할 것!

 

 

 

 

 

 

3. 코드 설명

 

import java.util.*;
import java.awt.Point;

public class Solution {
	
	static int[][] check, visit, a;
	static int[] dx = {0, 1, -1, 0}, dy = {1, 0, 0, -1};
	static int n, min = Integer.MAX_VALUE;
	
	public static void bfs() {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(0, 0));
		visit[0][0] = 1;
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			int x = p.x, y = p.y;
			
			if (x == n - 1 && y == n - 1)
				min = Math.min(check[x][y], min);
			
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i], ny = y + dy[i];
				if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
					if (visit[nx][ny] == 0 || check[nx][ny] > check[x][y] + a[nx][ny]) {
						check[nx][ny] = a[nx][ny] + check[x][y];
						q.offer(new Point(nx, ny));
						visit[nx][ny] = 1;
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int t = s.nextInt();
		
		for (int k = 0; k < t; k++) {
			n = s.nextInt();
			
			a = new int[n][n]; visit = new int [n][n]; check = new int [n][n];
			for (int i = 0; i < n; i++) {
				String str = s.next(); 
				for (int j = 0; j < n; j++)
					a[i][j] = str.charAt(j) - '0';
			}
			
			bfs();
		
			System.out.println("#" + (k + 1) + ": " + check[n-1][n-1]);
			for (int i = 0; i < n; i++) {
				Arrays.fill(visit[i], 0);
				Arrays.fill(check[i], 0);
			}
		}
	}
}

 

문제에서 배열을 숫자로 준 게 아니라 0101 이런 식을 input을 줬기 때문에 문자열로 받아서 처리해줬다.

그리고 이번에 문제를 풀면서 알게 된 것이 있는데 Point라는 자료형. C++에서의 Pair와 같은 것이다.

어쨌든 큐에 좌표를 넣고 돌면서 방문하지 않았거나 메모에 저장한 이동경로의 값이 새로운 경로의 값보다 작으면 값을 넣고 그다음 좌표를 큐에 넣어서 이동하는 방식이다. 이렇게 돌다가 결국 n-1, n-1 좌표에 여러 경로의 값이 도달하게 되면 그중 가장 작은 값을 정답으로 구하는 것이다.

그리고 이를 t번 반복하기 때문에 마지막에 배열들의 값을 0으로 리셋해주었다.