문제은행(BFS) 장기(JAVA)

1106 : 장기

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 834회    시도횟수: 2799회   

N×M장기판에 졸 한개와 말 한개가 놓여 있다. 말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다. 

 

말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자.

 

첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다.(1≤N, M≤100)

둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다. 

단, 장기판의 제일 왼쪽 위의 위치가 (1,1)이다.

각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다.

말이 졸을 잡기 위한 최소 이동 횟수를 출력한다.

[Copy] 9 9 3 5 2 8

[Copy] 2

?

1. /**************************************************************
2.     Problem: 1106
3.     User: a132034
4.     Language: Java
5.     Result: Success
6.     Time:146 ms
7.     Memory:9004 kb
8. ****************************************************************/
9.  
10.  
11. import java.util.LinkedList;
12. import java.util.Queue;
13. import java.util.Scanner;
14.  
15. public class Main {
16.  
17.  /*
18.   * 입력 - N M (장기판)
19.   * R C S K (말, 졸의 위치)
20.   * */
21.  
22.  @SuppressWarnings("resource")
23.  public static void main(String[] args) {
24.   int N, M, R, C, S, K;
25.   Queue<Point> queue = new LinkedList<Point>();
26.   Scanner sc = new Scanner(System.in);
27.   Point mal, zol;
28.   int[] x = {2,2,-2,-2,1,1,-1,-1};
29.   int[] y = {-1,1,-1,1,-2,2,-2,2};
30.  
31.    
32.   N = sc.nextInt();
33.   M = sc.nextInt();
34.   R = sc.nextInt();
35.   C = sc.nextInt();
36.   S = sc.nextInt();
37.   K = sc.nextInt();
38.    
39.   mal = new Point(R-1, C-1);
40.   zol = new Point(S-1, K-1);
41.    
42.   int[][] map = new int[N][M];
43.   for(int i = 0 ; i < N; ++i)
44.   {
45.    for(int j = 0; j < M; ++j)
46.    {
47.     map[i][j] = -1;
48.    }
49.   }
50.  
51.   map[mal.x][mal.y] = 0;  //말의 위치
52.   map[zol.x][zol.y] = -2; //졸의 위치
53.  
54.    
55.   queue.add(mal);
56.   while(!queue.isEmpty())
57.   {
58.    Point st, end;
59.    st = (Point) queue.remove();
60.    //시작점이 됨.
61.    
62.    //8방향
63.    for(int i = 0 ; i < 8; ++i)
64.    {
65.     int xMap = st.x + x[i];
66.     int yMap = st.y + y[i];
67.      
68.     if(xMap < 0 || xMap >= N || yMap < 0 || yMap >= M) //바운더리 처리
69.      continue;
70.      
71.     //한번 방문한 곳은 한번만
72.     if(map[xMap][yMap] != 0 && map[xMap][yMap] != -1 && map[xMap][yMap] != -2)
73.     {
74.      continue;
75.     }
76.      
77.     end = new Point(xMap, yMap);
78.  
79.     if(map[xMap][yMap] == -1) //이 지점을 방문한 적이 없다면
80.     {
81.      map[xMap][yMap] = map[st.x][st.y] + 1;//이전 인덱스 + 1
82.     }
83.     else if(map[xMap][yMap] == -2) //이 지점이 목표 지점이라면
84.     {
85.      map[xMap][yMap] = map[st.x][st.y] + 1;//이전 인덱스 + 1
86.      System.out.println(map[xMap][yMap]);
87.      return;
88.     }
89. //    else //지나갔던 지점이라면
90. //    {
91. //     if(map[xMap][yMap] > map[st.x][st.y] + 1) //더 빠른 경로로 올 수 있다면.
92. //      map[xMap][yMap] = map[st.x][st.y] + 1;
93. //    }
94.     queue.add(end);
95.    }
96.   }
97.    
98.    
99.    
100.  }
101.  
102.  static class Point
103.  {
104.    
105.   public int getX() {
106.    return x;
107.   }
108.   public void setX(int x) {
109.    this.x = x;
110.   }
111.   public int getY() {
112.    return y;
113.   }
114.   public void setY(int y) {
115.    this.y = y;
116.   }
117.    
118.   public int x;
119.   public int y;
120.    
121.   public Point(int x, int y) {
122.    super();
123.    this.x = x;
124.    this.y = y;
125.   }
126.  }
127.  
128. }

말의 위치로부터 8방향으로 갈 수 있음.Point 클래스는 좌표를 입력받기 위한 클래스

졸의 위치를 가기 위해 모든 방향으로 탐색을 해봐야 가장 적은 이동 횟수만으로 졸의 위치에 갈 수 있는 횟수를 알 수 있음.

BFS(넓이 우선 탐색)를 이용해서 전체 탐색

x, y배열을 각 8방향의 이동을 위하여 만든 것.

기본적으로 BFS는 queue를 이용해서 탐색.

첫 번째 위치(말의 위치) 에서 갈 수 있는 모든 좌표를 큐에 넣어주고 

큐에서 하나씩 꺼내어 다시 갈 수 있는 

위치를 넣어 줌.(count를 1씩 증가)

만약 지나간 위치를 다시 간다면 가장 적은 이동 횟수가 안되므로 제외. (주석은 무시..)

목표지점에 도착하면 그때의 count를 반환하며 종료.