import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;
/** 백트래킹 (DFS) */
public class Main {
static int n; // 도시의 크기
static int m; // 선택할 치킨집의 수
static int[][] map; // 도시의 정보
static ArrayList<Point> chicken = new ArrayList<Point>(); // 치킨집 정보
static ArrayList<Point> home = new ArrayList<Point>(); // 집의 정보
static boolean[] visited; /* [방법1] 치킨집 조합을 위한 방문 여부 */
static ArrayList<Point> selected; /* [방법2] 조합을 위해 선택한 치킨집 저장 */
static int minDis = Integer.MAX_VALUE; // 출력할 값. (도시의 최소 치킨 거리)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
map = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int num = sc.nextInt();
map[i][j] = num;
if (num == 2) // 치킨집이면
chicken.add(new Point(i, j));
else if (num == 1) // 집이면
home.add(new Point(i, j));
}
} // input 끝.
visited = new boolean[chicken.size()]; // [방법1]
selected = new ArrayList<>(); // [방법2]
dfs(0, 0);
System.out.println(minDis);
}
/** 조합: (치킨집의수)C(m) */
public static void dfs(int start, int depth) {
/* [출력] m개의 조합 완성 */
if (depth == m) {
int dis = 0; // 도시의 치킨 거리
// 모든 집에 대해서 m개의 치킨집과의 최소 거리들의 합을 구한다.
for (int i = 0; i < home.size(); i++) {
Point homeP = home.get(i);
int homeMinDis = Integer.MAX_VALUE; // 해당 집의 최소 치킨 거리
/* [방법1] 치킨집의 수만큼 반복 */
for (int j = 0; j < chicken.size(); j++) {
Point chickenP = chicken.get(j);
if (visited[j]) { // 방문한 치킨집이면 치킨 거리 계산
int homeDis = Math.abs(homeP.x - chickenP.x) + Math.abs(homeP.y - chickenP.y);
homeMinDis = Math.min(homeMinDis, homeDis);
}
}
/* [방법2] 치킨집 조합의 수만큼 반복 */
for (int j = 0; j < m; j++) {
Point chickenP = selected.get(j); // 조합으로 선택한 치킨집을 가져온다.
int homeDis = Math.abs(homeP.x - chickenP.x) + Math.abs(homeP.y - chickenP.y);
homeMinDis = Math.min(homeMinDis, homeDis);
}
dis += homeMinDis; // 해당 조합에 대한 도시의 치킨 거리
}
minDis = Math.min(minDis, dis); // 도시의 최소 치킨 거리를 구한다.
return;
}
/* [재탐색] 다음 치킨집 선택 */
else {
for (int i = start; i < chicken.size(); i++) {
/* [방법1] */
visited[i] = true; // 조합에 포함된 치킨집 방문 표시
dfs(i + 1, depth + 1); // 재귀
visited[i] = false; // backtracking(부모로 올라감.)
/* [방법2] */
selected.add(chicken.get(i)); // 해당 치킨집을 조합으로 선택
dfs(i + 1, depth + 1); // 재귀
selected.remove(selected.size() - 1); // backtracking(부모로 올라감.)
}
}
}
}- [방법2]의 수행속도가 조금 더 빠르다.
- [방법1]이 더 직관적이다.
import java.util.ArrayList;
import java.util.Scanner;
/**
* [시뮬레이션 규칙 찾기] 다음 세대에서 추가되는 선분의 방향이 규칙성을 가진다.
*
* 규칙성: 이전 세대 선분의 역순으로 이동하면서 (해당 선분의 방향 + 1, 단 0->3)을 하여 새로 추가된다.
*/
public class Main {
static int n; // 드래곤커브의 개수
// [주의1] 0:우, 1:상, 2:좌, 3:하
static int[] dx = { 1, 0, -1, 0 };
static int[] dy = { 0, -1, 0, 1 };
// [주의2] 범위 제대로 확인. 경계값이 포함되는지 항상 체크.
// 좌표에서 드래곤 커브가 차지하는지 여부
static boolean[][] visited = new boolean[101][101];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i++) {
// 드래곤커브를 만들고 그 좌표를 방문 표시한다.
makeDragonCurve(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
}
int res = 0;
/* 정사각형의 네 꼭짓점이 모두 드래곤커브의 일부인 것의 개수를 구한다. */
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
// 해당 좌표, 좌표의 오른쪽, 좌표의 아래쪽, 좌표의 오른쪽아래 대각선 체크
if (visited[i][j] && visited[i + 1][j] && visited[i][j + 1] && visited[i + 1][j + 1])
res++;
}
}
System.out.println(res);
}
/**
* @param x, y : 드래곤 커브의 시작점
* @param d : 시작 방향 0 (→,x축 증가), 1 (↑), 2 (←), 3(↓,y축 증가)
* @param g : 세대
*/
public static void makeDragonCurve(int x, int y, int d, int g) {
ArrayList<Integer> directions = new ArrayList();
directions.add(d); // 시작점 방향 추가
/* 세대수 만큼 반복하여 모든 선분의 방향을 구한다. */
for (int k = 0; k < g; k++) {
for (int i = directions.size() - 1; i >= 0; i--) {
// 1. 기존 선분들의 역순을 구한다.
int dir = directions.get(i);
// 2. (해당 선분의 방향 + 1, 단 0->3)을 하여 값을 변경한다.
dir = ((dir < 3) ? (dir + 1) : 0); // [방법1] 직관적이다.
dir = (dir + 1) % 4; // [방법2] 규칙성을 찾기 어려울 수 있다.
// 3. 뒤에 이어 붙인다.
directions.add(dir);
}
}
if (!visited[x][y])
visited[x][y] = true; // 시작점 방문 표시
/* 시작점부터 드래곤커브 방향을 따라 이동하면서 방문 표시 */
// [방법1] 매우 간단.
for (int dir : directions) {
x = x + dx[dir];
y = y + dy[dir];
visited[x][y] = true;
}
// [방법2] 조건이 까다로울 때, 좌표 범위 생각/이전의 좌표 기억/이전에 방문 여부 판단 등
for (int i = 0; i < directions.size(); i++) {
int dir = directions.get(i); // 0:우, 1:상, 2:좌, 3:하
int nx = x + dx[dir]; // 이동하는 다음 좌표
int ny = y + dy[dir];
// 드래곤커브의 좌표가 범위 내이고
if (nx >= 0 && nx <= 100 && ny >= 0 && ny <= 100) {
if (!visited[nx][ny]) // 방문하지 않았던 좌표면
visited[nx][ny] = true; // 드래곤커브 방문 표시
}
x = nx;
y = ny;
}
}
}import java.util.Scanner;
/** 백트래킹 (DFS) + 중간 종료 조건 */
public class Main {
static int n, m, h;
static boolean[][] visited;
static int res = -1;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); // 세로선의 개수, y
m = sc.nextInt(); // 가로선의 개수
h = sc.nextInt(); // 세로선마다 가로선을 놓을 수 있는 위치의 개수, x
visited = new boolean[h + 1][n + 1];
// 이미 존재하는 가로선을 방문 표시
for (int i = 0; i < m; i++) {
visited[sc.nextInt()][sc.nextInt()] = true;
}
// 선택할 수 있는 사다리의 수: 0 ~ 3개
for (int i = 0; i <= 3; i++) {
dfs(1, 0, i); // 가로선을 i개 추가하는 모든 경우의 수
// [종료] 가로선 추가 후 res값이 바뀌었으면 반복문 나감
if (res != -1)
break;
}
System.out.println(res);
}
public static void dfs(int x, int depth, int cnt) {
// [종료] res값이 바뀌었으면 조건을 만족하는 사다리를 완성했으므로 종료
if (res != -1)
return;
// [출력] 추가할 가로선을 cnt개 선택 시
if (depth == cnt) {
// 조건을 만족했으면 res값을 선택한 사다리의 수로 변경
if (rideLadder())
res = cnt;
return;
}
// [재탐색] 다음 추가해야 할 가로선 찾기
else {
for (int i = x; i <= h; i++) { // [중복 선택 제거]
for (int j = 1; j <= n - 1; j++) {
// [방법1]
// 현재 위치, 현재 위치의 왼쪽, 오른쪽이 기존 사다리에 포함되어 있지 않으면 현재 위치 추가 가능.
if (!visited[i][j] && !visited[i][j + 1] && !visited[i][j - 1]) {
visited[i][j] = true; // i, j 좌표인 가로선 선택
dfs(i, depth + 1, cnt); // 다음 가로선 찾기
visited[i][j] = false; // backtracking
}
// [방법2]
// 현재 위치에 가로선이 있으면 오른쪽으로 2칸 뛰어넘은 좌표 추가 가능.
if (visited[i][j]) {
j += 1;
continue;
}
// 현재 위치 오른쪽에 가로선이 있으면 오른쪽으로 3칸 뛰어넘은 좌표 추가 가능.
else if (visited[i][j + 1]) {
j += 2;
continue;
}
// 현재 위치와 현재 위치 오른쪽에 가로선이 없으면 현재 위치 추가 가능.
visited[i][j] = true; // i, j 좌표인 가로선 선택
dfs(i, depth + 1, cnt); // 다음 가로선 찾기
visited[i][j] = false; // backtracking
}
}
}
}
/* 모든 세로선에 대해 i번째 사다리 결과가 i인지 확인 */
public static boolean rideLadder() {
// 모든 세로선(y)에 대해 점검
for (int i = 1; i <= n; i++) {
int y = i;
// 가로선(x)의 위치가 h일 때까지 수행
for (int x = 1; x <= h; x++) {
if (visited[x][y]) // 해당 위치 확인
y++; // 오른쪽 이동
else if (visited[x][y - 1]) // 해당 위치 왼쪽 확인
y--; // 왼쪽 이동
}
// 하나의 세로선(y)이라도 결과가 맞지 않으면 실패
if (y != i)
return false;
}
return true;
}
}- [중복 선택 제거]
- 왼쪽->오른쪽으로 순회하므로 현재 순회 중인 x축을 다음 가로선을 찾을 때 넘겨주면 반복되는 조합 없앨 수 있음
- 즉, 사다리를 왼쪽->오른쪽, 위->아래 순으로 순회하면서 가로선을 추가할 수 있을 때 가로선을 추가한다.
- 이때 그 다음 추가할 가로선은 지금 추가한 가로선 보다 더 뒤에 있는 가로선을 고르므로
- 현재 x축의 값을 넘겨주어 넘겨준 x좌표 부터 순회하면 중복 선택을 줄일 수 있는 것이다.
- [종료]
- 조건을 만족했으면 res값을 선택한 사다리의 수로 변경하므로 이때가 최소로 선택할 수 있는 사다리 수 이다.
- 즉, res 값이 변하는 것이 종료 조건이 된다.
- [방법1]
- 해당 좌표의 전과 후의 가로선을 판단하여 해당 좌표를 가로선으로 넣을 수 있는지 확인하는 식
- [방법2]
- 해당 좌표을 기준으로 이 좌표 다음에 넣을 수 있는 좌표를 구하는 식
- (왼쪽->오른쪽, 위->아래 방향으로 탐색)
방법 1
import java.util.ArrayList;
import java.util.Scanner;
/** 브루트 포스 */
public class Main {
static int n, m;
// (우:0, 좌:1, 상:2, 하:3)
static int[] dx = { 0, 0, -1, 1 };
static int[] dy = { 1, -1, 0, 0 };
static final int RIGHT = 0;
static final int LEFT = 1;
static final int UP = 2;
static final int DOWN = 3;
static int[][] map;
static int[][] tmpMap;
static ArrayList<CCTV> cctv = new ArrayList();
static int res = Integer.MAX_VALUE; // 사각지대의 최소 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); // x
m = sc.nextInt(); // y
map = new int[n][m];
tmpMap = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int value = sc.nextInt();
map[i][j] = value;
if (value != 0 && value != 6) { // CCTV 추가
cctv.add(new CCTV(i, j, value));
}
}
} // input
dfs(0);
System.out.println(res);
}
public static void dfs(int depth) {
// [출력] 모든 cctv에 대한 회전 방향을 설정했으면, 사각지대의 최소 개수를 구한다.
if (depth == cctv.size()) {
// 감시 영역 표시를 위한 임시 맵
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
tmpMap[i][j] = map[i][j];
// 모든 cctv를 돌면서 각 cctv의 종류에 맞게 정해진 회전 방향에 대한 감시 시작
for (int i = 0; i < cctv.size(); i++) {
CCTV c = cctv.get(i);
rotate(c);
}
// 사각지대의 수 구하기
int blind = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (tmpMap[i][j] == 0)
blind++;
}
// 최소 사각지대의 수 변경
res = Math.min(res, blind);
return;
}
// [재탐색] 모든 CCTV에 대해 동쪽(E)부터 90도 회전하면서 탐색 수행 (E:0, S:1, W:2, N:3)
for (int i = 0; i < 4; i++) {
cctv.get(depth).setRot(i); // depth 번째 cctv의 회전 방향 설정
dfs(depth + 1); // depth+1 번째 cctv로 넘어감
}
}
/** 각 cctv의 종류에 맞게 정해진 회전 방향에 대한 감시 시작 */
// cctv마다 회전하는 방향(rotation)에서의 감시할 수 있는 방법이 다르다.
public static void rotate(CCTV c) {
// rotation: (E:0, S:1, W:2, N:3)
switch (c.num) {
case 1: // [→ 기준]
if (c.rot == 0) { // E -> 우
watch(c.x, c.y, RIGHT);
} else if (c.rot == 1) { // S -> 하
watch(c.x, c.y, DOWN);
} else if (c.rot == 2) { // W -> 좌
watch(c.x, c.y, LEFT);
} else if (c.rot == 3) { // N -> 상
watch(c.x, c.y, UP);
}
break;
case 2: // [←→ 기준]
if (c.rot == 0 || c.rot == 2) { // E, W -> 우좌
watch(c.x, c.y, RIGHT);
watch(c.x, c.y, LEFT);
} else if (c.rot == 1 || c.rot == 3) { // S, N -> 상하
watch(c.x, c.y, UP);
watch(c.x, c.y, DOWN);
}
break;
case 3: // [↑→ 기준]
if (c.rot == 0) { // E -> 우상
watch(c.x, c.y, RIGHT);
watch(c.x, c.y, UP);
} else if (c.rot == 1) { // S -> 우하
watch(c.x, c.y, RIGHT);
watch(c.x, c.y, DOWN);
} else if (c.rot == 2) { // W -> 좌하
watch(c.x, c.y, LEFT);
watch(c.x, c.y, DOWN);
} else if (c.rot == 3) { // N -> 좌상
watch(c.x, c.y, LEFT);
watch(c.x, c.y, UP);
}
break;
case 4: // [←↑→ 기준]
if (c.rot == 0) { // E -> 상좌우
watch(c.x, c.y, UP);
watch(c.x, c.y, LEFT);
watch(c.x, c.y, RIGHT);
} else if (c.rot == 1) { // S -> 상하우
watch(c.x, c.y, UP);
watch(c.x, c.y, DOWN);
watch(c.x, c.y, RIGHT);
} else if (c.rot == 2) { // W -> 하좌우
watch(c.x, c.y, DOWN);
watch(c.x, c.y, LEFT);
watch(c.x, c.y, RIGHT);
} else if (c.rot == 3) { // N -> 상하좌
watch(c.x, c.y, UP);
watch(c.x, c.y, DOWN);
watch(c.x, c.y, LEFT);
}
break;
case 5:
watch(c.x, c.y, UP); // 상
watch(c.x, c.y, DOWN); // 하
watch(c.x, c.y, RIGHT); // 좌
watch(c.x, c.y, LEFT); // 우
break;
}
}
/** x, y를 시작으로 dir 방향으로 감시 (우:0, 좌:1, 상:2, 하:3) */
// 상하좌우 방향에 따라 감시할 수 있는 모든 곳에 감시 표시
public static void watch(int x, int y, int dir) {
// direction: (우:0, 좌:1, 상:2, 하:3)
switch (dir) {
case RIGHT: // 우(y++)
for (int j = y; j < m; j++) {
if (tmpMap[x][j] == 6) // 벽이면 멈춘다.
break;
if (tmpMap[x][j] == 0) // 빈칸이면 감시 표시
tmpMap[x][j] = -1;
}
break;
case LEFT: // 좌(y--)
for (int j = y; j >= 0; j--) {
if (tmpMap[x][j] == 6) // 벽이면 멈춘다.
break;
if (tmpMap[x][j] == 0) // 빈칸이면 감시 표시
tmpMap[x][j] = -1;
}
break;
case UP: // 상(x--)
for (int i = x; i >= 0; i--) {
if (tmpMap[i][y] == 6) // 벽이면 멈춘다.
break;
if (tmpMap[i][y] == 0) // 빈칸이면 감시 표시
tmpMap[i][y] = -1;
}
break;
case DOWN: // 하(x++)
for (int i = x; i < n; i++) {
if (tmpMap[i][y] == 6) // 벽이면 멈춘다.
break;
if (tmpMap[i][y] == 0) // 빈칸이면 감시 표시
tmpMap[i][y] = -1;
}
break;
}
}
public static class CCTV {
int x;
int y;
int num; // cctv 종류
int rot; // 회전 방향 (E:0, S:1, W:2, N:3)
public CCTV(int x, int y, int num) {
this.x = x;
this.y = y;
this.num = num;
this.rot = 0; // E부터 시작
}
public void setRot(int rot) {
this.rot = rot;
}
}
}방법 2
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static Scanner s = new Scanner(System.in);
static int n, m, res = Integer.MAX_VALUE;
static int[][] map;
static final int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;
static ArrayList<CCTV> CCTVList = new ArrayList<>();
public static void main(String[] args) {
n = s.nextInt();
m = s.nextInt();
map = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = s.nextInt();
if (1 <= map[i][j] && map[i][j] <= 5) {
CCTVList.add(new CCTV(i, j, map[i][j])); // CCTV 추가
}
}
}
search(0, map);
System.out.println(res);
}
private static void search(int count, int[][] visited) {
if (count == CCTVList.size()) { // 사각지대 개수 계산
int zeroCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == 0) {
zeroCount++;
}
}
}
res = Math.min(res, zeroCount);
return;
}
CCTV cctv = CCTVList.get(count);
int x = cctv.x;
int y = cctv.y;
int cctvNum = cctv.num;
int[][] newVisited = new int[n][m];
switch (cctvNum) {
case 1: // 4가지 경우
for (int i = 0; i < 4; i++) {
copyArray(newVisited, visited); // 현재 visited 상태 복사
detect(newVisited, x, y, i); // 현재 i에 대해 감시 (0: 상, 1: 좌, 2: 하, 3: 우)
search(count + 1, newVisited); // 다음 CCTV 모든 감시 방향 탐색
}
break;
case 2: // 2가지 경우
for (int i = 0; i < 2; i++) {
copyArray(newVisited, visited);
detect(newVisited, x, y, i); // 0, 3 / 1, 3 감시
detect(newVisited, x, y, i + 2);
search(count + 1, newVisited);
}
break;
case 3: // 4가지 경우
for (int i = 0; i < 4; i++) {
copyArray(newVisited, visited);
detect(newVisited, x, y, i); // 0, 1 / 1, 2 / ... 감시
detect(newVisited, x, y, (i + 1) % 4);
search(count + 1, newVisited);
}
break;
case 4: // 4가지 경우
for (int i = 0; i < 4; i++) {
copyArray(newVisited, visited);
detect(newVisited, x, y, i); // 0, 1, 2 / 1, 2, 3 / ... 감시
detect(newVisited, x, y, (i + 1) % 4);
detect(newVisited, x, y, (i + 2) % 4);
search(count + 1, newVisited);
}
break;
case 5: // 1가지 경우
copyArray(newVisited, visited);
for (int i = 0; i < 4; i++) { // 0, 1, 2, 3 모두 감시
detect(newVisited, x, y, i);
}
search(count + 1, newVisited);
break;
}
}
private static void detect(int[][] visited, int x, int y, int direction) {
switch (direction) {
case UP:
for (int i = y; i >= 0; i--) { // 현재 위치에에서 위쪽 방향 벽에 닿을때까지 감시
if (map[x][i] == 6) {
break;
}
visited[x][i] = -1;
}
break;
case LEFT:
for (int i = x; i >= 0; i--) { // 현재 위치에에서 왼쪽 방향 벽에 닿을때까지 감시
if (map[i][y] == 6) {
break;
}
visited[i][y] = -1;
}
break;
case DOWN:
for (int i = y; i < m; i++) { // 현재 위치에에서 아래쪽 방향 벽에 닿을때까지 감시
if (map[x][i] == 6) {
break;
}
visited[x][i] = -1;
}
break;
case RIGHT:
for (int i = x; i < n; i++) { // 현재 위치에에서 오른쪽 방향 벽에 닿을때까지 감시
if (map[i][y] == 6) {
break;
}
visited[i][y] = -1;
}
break;
}
}
private static void copyArray(int[][] arr1, int[][] arr2) {
for (int i = 0; i < n; i++) {
arr1[i] = Arrays.copyOf(arr2[i], m);
}
}
public static class CCTV {
int x, y, num;
public CCTV(int x, int y, int num) {
this.x = x;
this.y = y;
this.num = num;
}
}
}- [방법1] CCTV의 방향을 완전 탐색으로 설정 후에 그 방향에 따라 한꺼번에 모든 CCTV 감시
- [방법2] CCTV 하나 방향 설정하고 감시, 다음 CCTV 방향 설정하고 감시, ... 반복