[백준]_7562_나이트의이동, 2178_미로 탐색

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

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 B7562 {
	static int T, I, x, y;
	static int[][] delta = {{-2,-1},{2,-1},{-2,1},{2,1},{1,2},{-1,2},{1,-2},{-1,-2}};
	static boolean[][] visited;
	static Point start,end;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		T = parse(br.readLine());

		for (int i = 0; i < T; i++) {
			I = parse(br.readLine());
			visited = new boolean[I][I];
			
			st = new StringTokenizer(br.readLine());
			start = new Point(parse(st.nextToken()),parse(st.nextToken()),0); 
			st = new StringTokenizer(br.readLine());
			end = new Point(parse(st.nextToken()),parse(st.nextToken()),0);
			System.out.println(end.y);
			sb.append(gozero(start)).append("\n");
		}
		System.out.println(sb);
	}
	
	static int gozero(Point at) {
		Queue<Point> q = new LinkedList<>();
		q.offer(at);
		visited[at.x][at.y] = true;

		while (!q.isEmpty()) {
			// queue에서 point 뽑기
			Point p = q.poll();
			// end일 경우 끝내기
			if (p.x == end.x && p.y == end.y) {
				return p.cnt;
			}

			for (int d = 0; d < 8; d++) {
				int dx = p.x + delta[d][0];
				int dy = p.y + delta[d][1];

				// 방문 안 했을 때 queue에 넣기
				if (inside(dx,dy) && !visited[dx][dy]){
					visited[dx][dy] = true;
					q.offer(new Point(dx, dy, p.cnt + 1));
				}
			}
		}
		// 모든 경우를 탐색하고 나오지 않을 때
		return -1;
		
	}
	
	static int parse(String s) {
		return Integer.parseInt(s);
	}

	static boolean inside(int nx, int ny) {
		return nx >= 0 && nx < I && ny >= 0 && ny < I;
	}

}

class Point{
	int x;
	int y;
	int cnt;
	public Point(int x, int y,int cnt) {
		this.x = x;
		this.y = y;
		this.cnt = cnt;
	}
	
}

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

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 B2178 {
	static int N, M;
	static char[][] field;
	static int[][] delta = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static Point start, end;
	static boolean[][] visited;

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		field = new char[N][M];
		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			field[i] = br.readLine().toCharArray();
		}
		start = new Point(0, 0, 0);
		end = new Point(N - 1, M - 1, 0);

		System.out.println(goend(start)+1);

	}

	static int goend(Point at) {
		Queue<Point> q = new LinkedList<>();
		q.offer(at);
		visited[at.x][at.y] = true;
		while (!q.isEmpty()) {
			// q에서 새로운 point 뽑기
			Point p = q.poll();
			// end면 종료
			if (p.x == end.x && p.y == end.y) {
				return p.cnt;
			}
			for (int d = 0; d < 4; d++) {
				int dx = p.x + delta[d][0];
				int dy = p.y + delta[d][1];
				
				// 방문 안 한 곳이 1이면 queue에 넣기
				if (inside(dx, dy) && !visited[dx][dy] && field[dx][dy] == '1') {
					visited[dx][dy] = true;
					q.offer(new Point(dx, dy, p.cnt + 1));
				}
			}
		}
		// 끝까지 가기 실패
		return -1;
	}

	static boolean inside(int nx, int ny) {
		return nx >= 0 && nx < N && ny >= 0 && ny < M;
	}

}

class Point {
	int x;
	int y;
	int cnt;

	public Point(int x, int y, int cnt) {
		this.x = x;
		this.y = y;
		this.cnt = cnt;
	}
}