[swexpert] 1249. 보급로 (swexpert, java, c++, bfs)

1. java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Pos{
	int y,x;

	public Pos(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
}

public class Solution {
	static int t,n;
	static int[][] map;
	static int[] xpos= {1,-1,0,0};
	static int[] ypos= {0,0,1,-1};
	static int[][] vis;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			map=new int[n][n];
			vis=new int[n][n];
			for (int i = 0; i <n; i++) {
				Arrays.fill(vis[i], -1);
			}
			for (int i = 0; i < n; i++) {
				String s=sc.next();
				for (int j = 0; j < n; j++) {
					map[i][j]=s.charAt(j)-'0';
				}
			}
			Queue<Pos> q=new LinkedList<Pos>();
			q.add(new Pos(0,0));
			vis[0][0]=0;
			while(q.size()!=0) {
				Pos cur=q.poll();
				int y=cur.y;
				int x=cur.x;
				for (int k = 0; k <4; k++) {
					int yy=y+ypos[k];
					int xx=x+xpos[k];
					if(xx<0 || yy<0 || xx>=n || yy>=n)continue;
					if(vis[yy][xx]==-1 || vis[y][x]+map[yy][xx]<vis[yy][xx]) {
						vis[yy][xx]=vis[y][x]+map[yy][xx];
						q.add(new Pos(yy,xx));
					}	
				}
			}
			
			System.out.printf("#%d %d\n",tc,vis[n-1][n-1]);
		}
		
	}
}

 

2. C++ 풀이

 

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

#define MAX 101
#define INF 987654321
int n,t;
int map[MAX][MAX];
int dist[MAX][MAX];
int ypos[] = { 0,0,1,-1 };
int xpos[] = { 1,-1,0,0 };


void bfs() {
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	dist[0][0] = 0;

	while (q.size() > 0) {
		int y, x;
		tie(y, x) = q.front();
		q.pop();
		//cout << y << "," << x << "\n";
			for (int k = 0; k < 4; k++) {
			int yy = y + ypos[k];
			int xx = x + xpos[k];
			if (xx < 0 || yy < 0 || xx >= n || yy >= n)continue;
			if (dist[yy][xx] > dist[y][x]+map[yy][xx]) {
					dist[yy][xx] = dist[y][x] + map[yy][xx];
					q.push({ yy,xx });
				
			}

		}

	}


}

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		cin >> n;
		char ch;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> ch;
				map[i][j]=ch-'0';
				dist[i][j] = INF;
			}
		}

		bfs();

		cout << "#" << tc << " "<<dist[n-1][n-1]<<"\n";

	}


	return 0;
}