[백준 2178] 미로찾기 (C++, Java)

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

 

문제풀이

• 입력 받는 부분 tip (String 으로 받아도 -'0' 해주면 int로 돌아온다.

		map = new int[R][C];
		visit= new boolean[R][C];
		for(int i =0 ; i <R ; i++)
		{
			String input1 = br.readLine();
			for(int j = 0 ; j < C ; j++ )
			{
				map[i][j] = input1.charAt(j) - '0'; 
			}
		}

• BFS를 돌면서 이동 가능한 칸은 자기자신의 숫자+1 결국 (최단거리)

C++ 

#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;


int ar[101][101];
int vi[101][101];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n, m, ans = 1000000;

queue<pair<int, int>> q;




void input()
{
	cin >> n >> m;
	// nxm 짜리 
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &ar[i][j]); //꿀팁
		}
	}
}

void bfs() {
	q.push({ 0, 0 });
	vi[0][0] = 1;
	ar[0][0] = 0;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (x == n - 1 && y == m - 1)
		{
			ans = vi[x][y];
			break;
		}


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

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

			if (vi[nx][ny] == 0 && ar[nx][ny] == 1)
			{
				
				vi[nx][ny] = vi[x][y] + 1;
				q.push({ nx, ny });
			}

		}

	}

}

void dfs(int x, int y, int su) {
	if (x == n - 1 && y == m - 1) {
		ans = min(su, ans);
		return;
	}

	for (int w = 0; w < 4; w++)
	{
		int nx = x + dx[w];
		int ny = y + dy[w];
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		if (vi[nx][ny] == 0 && ar[nx][ny] == 1) 
		{
			
			vi[nx][ny] = vi[x][y] + 1;
			dfs(nx, ny, vi[nx][ny]);
			vi[nx][ny] = 0;
		}
	}
}

int main()
{
	input();
	bfs();
	cout << ans  << endl;
	return 0;
}

 

Java

package Z_ShinHanCard_Prepare;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Box
{
	int x;
	int y;
	int z;
	public Box(int x, int y)
	{
		this.x = x;
		this.y = y;
		this.z = z;
	}
}
public class D2백준2178_미로탐색_DFSBFS 
{
	static int R,C,Z;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx = { -1,1,0,0};
	static int[] dy = { 0,0,-1,1};
	
	static void bfs(int x, int y)
	{
		Queue<Box> q = new LinkedList<Box>(); 
		q.add(new Box(x,y));
		while(!q.isEmpty())
		{
			Box box = q.poll();
			for(int w=  0 ; w< 4 ; w++)
			{
				int nx = box.x + dx[w];
				int ny = box.y +dy[w];
				if(nx<0 || nx>=R || ny <0 || ny >=C)
					continue;
				if(visit[nx][ny])
					continue;
				if(map[nx][ny] == 0)
					continue;
				q.add(new Box(nx,ny));
				visit[nx][ny] = true;
				box.z = map[nx][ny]+1;
				map[nx][ny] = map[box.x][box.y] + 1;
						
			}
			
			
		}
	}
	public static void main(String[] args) throws IOException 
	{
		
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st= new StringTokenizer(input);
		R= Integer.parseInt(st.nextToken()); //4
		C= Integer.parseInt(st.nextToken()); //6
		
		map = new int[R][C];
		visit= new boolean[R][C];
		for(int i =0 ; i <R ; i++)
		{
			String input1 = br.readLine();
			for(int j = 0 ; j < C ; j++ )
			{
				map[i][j] = input1.charAt(j) - '0'; 
			}
		}
		
		visit[0][0] =true;
		bfs(0,0);
		System.out.println(map[R-1][C-1]);
		

	}

}