https://www.acmicpc.net/problem/14503
14503번: 로봇 청소기
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음
www.acmicpc.net
시뮬레이션 문제로 풀었습니다.
문제에서 설명하는대로 구현하면 되기 때문에 문제를 잘 읽으려고 많이 노력했습니다.
그리고 기능단위별로 함수를 만들려고 시도했습니다.
무조건 왼쪽으로 돌면서 4방위를 모두 살피게 되는데 이 기능을 함수로 표현하지 못한건 아쉬웠습니다.
package com.company;
import java.util.Scanner;
public class boj14503 {
static int N, M;
static int x, y, d;
static int[][] map;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = 0;
N = sc.nextInt();
M = sc.nextInt();
x = sc.nextInt();
y = sc.nextInt();
d = sc.nextInt();
// d = 0 북, 1 = 동, 2 = 남, 3 = 서
map = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
}
}
while (true) {
// System.out.println(x + " " + y + " " + d);
if (map[x][y] == 0) {
map[x][y] = 2;
count++;
}
//종료 조건
if (allClearOrWall() && backWall()) { // map 주변이 allClear 또는 wall && 뒤에 후진하는게 back
break;
} else if (allClearOrWall() && !backWall()) {
stepBack();
continue;
} else {
if (d == 0) { // 북
if (map[x][y - 1] == 0) { // 청소 가능
d = 3;
y = y - 1;
} else if (map[x][y - 1] == 1 && map[x + 1][y] != 1 && allClearOrWall()) { // 벽
stepBack();
} else {
d = 3;
}
continue;
// if (map[x][y - 1] == 0) { // 청소 가능
// d = 3;
// y = y - 1;
// } else if (map[x][y - 1] == 1 && map[x + 1][y] != 1) { // 벽
// stepBack();
// } else {
// d = 3;
// }
} else if (d == 1) { // 동
if (map[x - 1][y] == 0) {
d = 0;
x = x - 1;
} else if (map[x - 1][y] == 1 && map[x][y - 1] != 1 && allClearOrWall()) {
stepBack();
} else {
d = 0;
}
continue;
} else if (d == 2) { //남
if (map[x][y + 1] == 0) {
d = 1;
y = y + 1;
} else if (map[x][y + 1] == 1 && map[x - 1][y] != 1 && allClearOrWall()) {
stepBack();
} else {
d = 1;
}
continue;
} else { //서
if (map[x + 1][y] == 0) {
d = 2;
x = x + 1;
} else if (map[x + 1][y] == 1 && map[x][y + 1] != 1 && allClearOrWall()) { // 스텝백을 뒤로 할 수 있어야한다.
stepBack();
} else {
d = 2;
}
continue;
}
}
}
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < M; j++) {
// System.out.print(" "+map[i][j]);
// }
// System.out.println();
// }
System.out.println(count);
}
static boolean allClearOrWall() {
if (map[x - 1][y] == 0 || map[x + 1][y] == 0 || map[x][y - 1] == 0 || map[x][y + 1] == 0) {
return false;
} else {
return true;
}
}
static boolean backWall() {
if (d == 0 && map[x + 1][y] == 1) { // 북
return true;
} else if (d == 1 && map[x][y - 1] == 1) { // 동
return true;
} else if (d == 2 && map[x - 1][y] == 1) { //남
return true;
} else if (d == 3 && map[x][y + 1] == 1) { //서
return true;
} else {
return false;
}
}
static void stepBack() {
if (d == 0) { // 북
x = x + 1;
} else if (d == 1) { // 동
y = y - 1;
} else if (d == 2) { //남
x = x - 1;
} else { //서
y = y + 1;
}
}
}
'알고리즘' 카테고리의 다른 글
백준 14502 - 연구소(새 풀이) (0) | 2020.05.11 |
---|---|
SWEA - 벌꿀채취 (0) | 2020.05.11 |
백준 - 14502 연구소 (0) | 2020.04.26 |
백준 14889 - 스마트와 링크 (0) | 2020.04.26 |
백준 17144번 - 미세먼지 안녕!(런타임 에러) (0) | 2020.04.26 |