View

λ°˜μ‘ν˜•

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

 

SW Expert Academy

SW ν”„λ‘œκ·Έλž˜λ° μ—­λŸ‰ 강화에 도움이 λ˜λŠ” λ‹€μ–‘ν•œ ν•™μŠ΅ 컨텐츠λ₯Ό ν™•μΈν•˜μ„Έμš”!

swexpertacademy.com

 

 

package SWEA;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Solution_1249 {
	static int map[][];
	static int N, res;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int t = 1; t < T + 1; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];

			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = s.charAt(j) - '0';
				}
			}
			res = 0;
			bfs();
			System.out.println("#" + t + " " + res);

		}
	}

	private static void bfs() {
		// μš°μ„ μˆœμœ„ 큐 μ‚¬μš©
		PriorityQueue<Node> que = new PriorityQueue<>();
		boolean visit[][] = new boolean[N][N];
		visit[0][0] = true;
		que.add(new Node(0, 0, map[0][0]));

		while (!que.isEmpty()) {
//			Iterator iterator = que.iterator();
//			while (iterator.hasNext())
//				System.out.println(iterator.next() + " ");
			Node node = que.poll();

			if (node.x == N - 1 && node.y == N - 1) {
				res = node.time;
				return;
			}

			for (int i = 0; i < 4; i++) {
				int nx = dx[i] + node.x;
				int ny = dy[i] + node.y;

				// 첫 λΉ„κ΅λŒ€μƒ μ΄ˆκΈ°ν™”
				if (nx >= 0 && ny >= 0 && nx < N && ny < N && visit[ny][nx] != true) {
					// μ‹œκ°„ κ°±μ‹ ν•΄μ„œ μš°μ„ μˆœμœ„ 큐에 λ„£μŒ
					int totalTime = node.time + map[ny][nx];
					que.add(new Node(ny, nx, totalTime));
					visit[ny][nx] = true;

				}
			}
		}

	}

	static public class Node implements Comparable<Node> {
		int x, y, time;

		public Node(int y, int x, int time) {
			this.y = y;
			this.x = x;
			this.time = time;
		}

		@Override
		// λ³΅κ΅¬μ‹œκ°„μ΄ μž‘μ„μˆ˜λ‘ -> μ˜€λ¦„μ°¨μˆœ μ •λ ¬
		public int compareTo(Node o) {
			return this.time - o.time;
		}

		@Override
		public String toString() {
			return "Node [x=" + x + ", y=" + y + ", time=" + time + "]";
		}

	}

}

bfs만 μ¨μ„œ 풀라고 ν–ˆλŠ”λ° μ‰½κ²Œ 될리가 읍지,,

μš°μ„ μˆœμœ„ 큐λ₯Ό μ‚¬μš©ν•˜κ±°λ‚˜ ν˜Ήμ€ dp+bfs둜 ν‘ΈλŠ” 방법이 μžˆλŠ”λ“―

λ‚˜λŠ” μš°μ„ μˆœμœ„ 큐λ₯Ό μ‚¬μš©ν•΄μ„œ time이 적게 κ±Έλ¦¬λŠ” 순으둜 μ˜€λ¦„μ°¨μˆœ μ‹œν‚΄ 

 

 

λ°˜μ‘ν˜•
Share Link
reply
λ°˜μ‘ν˜•
Β«   2024/11   Β»
일 μ›” ν™” 수 λͺ© 금 ν† 
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30