문제
주어진 NxM의 체스판에 Knight, Queen, Pawn이 주어질 때, 이 말들을 움직였을 때 잡힐 수 없는 안전한 칸의 개수를 구하는 문제
Knight : 2x3의 직사각 형을 만들 었을 때, 해당 점에서 가장 먼 점으로만 이동할 수 있다. 중간에 다른 말이 있어도 영향을 받지 않는다.
Queen : 가로, 세로, 대각선으로 쭉 움직일 수 있다. 단, 중간에 다른 말이 있다면 그 전까지만 이동할 수 있다.
Pawn : 움직이지 못하고 그저 장애물 역할만 한다.
접근방법
주어진대로 노가다 코드를 짜면 얼마든지 해결할 수 있다.
즉, 먼저 Queen이 갈 수 있는 범위를 체크하고, 그 다음으로 Knight가 갈 수 있는 범위를 체크하고, 해당 말 들이 없는 칸들의 개수를 세서 출력해주면 된다.
먼저 queen, knight의 위치를 ArrayList에 저장하고, char배열인 맵의 해당 위치에 각 말의 알파벳(K, Q, P)을 넣어준다.
각 queen, knight를 정해진 규칙에 따라 이동하도록 하고, 이동한 좌표는 'o'로 바꾸어 준다.
각 말들이 이동하지 않은 곳은 char의 초기값인 '\u0000'이 들어있으므로, 이러한 원소들의 개수를 확인해 출력해준다.
같은 스터디원의 코드를 참고해 더 깔끔하게 코드를 수정해 보았다.
dx, dy 배열을 이용하면 규칙이 없더라도 for문으로 돌릴 수 있다.
for(int i=0; i<8; i++){
int next_x = x;
int next_y = y;
while(true) {
next_x += dx[i];
next_y += dy[i];
if(next_x < 0 || next_x >= N || next_y < 0 || next_y >= M)
break; // map 범위를 벗어나는 경우
if(map[next_x][next_y] == 'K'
|| map[next_x][next_y] == 'Q'
|| map[next_x][next_y] == 'P' )
break; // 말이 지나갈 수 없는 경우(K/P/Q)
map[next_x][next_y] = 'o';
}
}
knight의 움직임 경우에는 아래와 같이 코드를 짤 수 있다.
int[] dx = {2, 2, 1, 1, -1, -1, -2, -2};
int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};
for(int i=0; i<8; i++){
int next_x = x + dx[i];
int next_y = y + dy[i];
if(next_x >= 0 && next_x < N
&& next_y >=0 && next_y < M){ // 배열 범위 내에 있으면서
if(map[next_x][next_y] == '\u0000') // 빈칸일 경우
map[next_x][next_y] = 'o';
}
}
소스코드
static int N, M;
static char[][] map;
static class Pos{
int x; int y;
public Pos(int x, int y) {this.x = x; this.y = y;}
}
static void checkQueen(int x, int y){
int[] dx = {1, -1, 0, 0, 1, 1, -1, -1};
int[] dy = {0, 0, 1, -1, 1, -1, 1, -1};
for(int i=0; i<8; i++){
int next_x = x;
int next_y = y;
while(true) {
next_x += dx[i];
next_y += dy[i];
if(next_x < 0 || next_x >= N || next_y < 0 || next_y >= M)
break; // map 범위를 벗어나는 경우
if(map[next_x][next_y] == 'K'
|| map[next_x][next_y] == 'Q'
|| map[next_x][next_y] == 'P' )
break; // 말이 지나갈 수 없는 경우(K/P/Q)
map[next_x][next_y] = 'o';
}
}
}
static void checkKnight(int x, int y){
int[] dx = {2, 2, 1, 1, -1, -1, -2, -2};
int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};
for(int i=0; i<8; i++){
int next_x = x + dx[i];
int next_y = y + dy[i];
if(next_x >= 0 && next_x < N
&& next_y >=0 && next_y < M){ // 배열 범위 내에 있으면서
if(map[next_x][next_y] == '\u0000') // 빈칸일 경우
map[next_x][next_y] = 'o';
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] input = in.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
map = new char[N][M];
ArrayList<Pos> queen = new ArrayList<>();
ArrayList<Pos> knight = new ArrayList<>();
// input
for(int i=0; i<3; i++){
input = in.readLine().split(" ");
int num = Integer.parseInt(input[0]);
for(int j=1; j<=num; j++){
int x = Integer.parseInt(input[2*j-1]) - 1;
int y = Integer.parseInt(input[2*j]) - 1;
if(i==0){
queen.add(new Pos(x,y));
map[x][y] = 'Q';
}else if(i==1){
knight.add(new Pos(x,y));
map[x][y] = 'K';
}else{
map[x][y] = 'P';
}
}
}
// queen check
for(int i=0; i<queen.size(); i++)
checkQueen(queen.get(i).x, queen.get(i).y);
// knight check
for(int i=0; i<knight.size(); i++)
checkKnight(knight.get(i).x, knight.get(i).y);
int answer = 0;
for(int i=0; i<N; i++)
for(int j=0; j< M; j++)
if(map[i][j] == '\u0000')
++answer;
System.out.println(answer);
}'알고리즘' 카테고리의 다른 글
| [JAVA] 백준 1406 : 에디터 (0) | 2019.02.16 |
|---|---|
| [JAVA] 백준 1347 : 미로만들기 (0) | 2019.02.06 |
| [JAVA] 백준 2512 : 예산 (0) | 2019.02.02 |
| [JAVA] 백준 3985 : 롤케이크 (0) | 2019.02.01 |
| [JAVA] 백준 10610 : 30 (0) | 2019.02.01 |
