[Baekjoon] 6146_신아를 만나러

Silver I

문제(출처: https://www.acmicpc.net/problem/6146)

---

< 신아를 만나러 >

 

문제 풀이 

 

bfs 탐색을 통해 웅덩이를 제외한 곳을 방문하며 최소 거리를 구한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _6146_ { // 신아를 만나러
	static int arr[][], x, y;
	static boolean visited[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		x = Integer.parseInt(st.nextToken()) + 500;
		y = Integer.parseInt(st.nextToken()) + 500;
		int n = Integer.parseInt(st.nextToken());

		arr = new int[1001][1001];
		visited = new boolean[1001][1001];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken()) + 500;
			int b = Integer.parseInt(st.nextToken()) + 500;

			visited[a][b] = true;
		}

		bfs();

	}

	private static void bfs() {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { 500, 500, 0 });

		while (!queue.isEmpty()) {
			int num[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int a = num[0] + dx[i];
				int b = num[1] + dy[i];
				if (Math.abs(a) <= 1001 && Math.abs(b) <= 1001 && !visited[a][b]) {
					visited[a][b] = true;
					if (a == x && b == y) {
						System.out.println(num[2] + 1);
						return;
					}
					queue.add(new int[] { a, b, num[2] + 1 });
				}
			}
		}
	}
}

 

Main

변수)
arr : 거리 저장
x, y : 집 위치
visited : 방문 여부
dx, dy : 상하좌우 

 

- 집 위치(x, y), n 입력

- (a, b) 입력받아 방문 표시

- bfs 함수 호출

 

bfs

- queue에 [시작 위치 x, y, 거리] 추가

- queue가 빌 때까지 반복

: queue에서 값을 꺼내와 상하좌우로 이동

: 이동한 위치가 범위 안이며 아직 방문하지 않은 곳이라면 이동

: 이동한 위치가 집 위치라면 종료

---

---