https://www.acmicpc.net/problem/15683
카메라마다 바라볼 수 있는 모든 경우의 수를 계산해 dfs로 풀었다.
처음에는 메모리 좀 아껴보겠다고 감시 방향을 map에 -1로 표시했다가 다시 0으로 초기화하는 방법을 썼는데, 다른 카메라가 바라보는 경로인데도 0으로 초기화하는 경우가 생겨 오답이 나왔다.
map을 복사해서 dfs를 하는 방식으로 구현하니 정답이었다..
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static List<int[]> cctvList;
static int N, M;
static int tvNum = 0, answer = Integer.MAX_VALUE;
// 상 우 하 좌
static int[] dr = { -1, 0, 1, 0 };
static int[] dc = { 0, 1, 0, -1 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
N = Integer.parseInt(stk.nextToken());
M = Integer.parseInt(stk.nextToken());
int[][] map = new int[N][M];
cctvList = new ArrayList<int[]>();
// map 입력
for (int i = 0; i < N; i++) {
stk = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(stk.nextToken());
if (isCCTV(map[i][j])) {
cctvList.add(new int[] { i, j });
}
}
}
// cctv의 개수
tvNum = cctvList.size();
dfs(0, map);
System.out.println(answer);
}
private static void dfs(int cnt, int[][] map) {
if (cnt == tvNum) {
// 모든 cctv의 방향을 체크했다면 사각지대 크기 구함
answer = Math.min(answer, getBlind(map));
return;
}
int i = cctvList.get(cnt)[0];
int j = cctvList.get(cnt)[1];
int[][] tmp = new int[N][M];
for (int d = 0; d < 4; d++) {
copyMap(map, tmp); // map 복사
// cctv 종류에 따라 다르게 처리
switch (map[i][j]) {
case 1:
// 한 방향만 감시
fill(tmp, i, j, d, -1);
dfs(cnt + 1, tmp);
break;
case 2:
// 상하 / 좌우 2가지로만 감시 가능
// -> 2번만 반복해도 됨
if (d > 1) break;
// 반대방향 감시
fill(tmp, i, j, d, -1);
fill(tmp, i, j, (d + 2) % 4, -1);
dfs(cnt + 1, tmp);
break;
case 3:
// 직각 방향 감시
fill(tmp, i, j, d, -1);
fill(tmp, i, j, (d + 1) % 4, -1);
dfs(cnt + 1, tmp);
break;
case 4:
// 한 방향만 빼고 감시
fill(tmp, i, j, d, -1);
fill(tmp, i, j, (d + 1) % 4, -1);
fill(tmp, i, j, (d + 2) % 4, -1);
dfs(cnt + 1, tmp);
break;
case 5:
if (d > 0) break; // 한 번만 반복해도 됨
// 모든 방향 감시
fill(tmp, i, j, d, -1);
fill(tmp, i, j, (d + 1) % 4, -1);
fill(tmp, i, j, (d + 2) % 4, -1);
fill(tmp, i, j, (d + 3) % 4, -1);
dfs(cnt + 1, tmp);
break;
}
}
return;
}
// map 복사
private static void copyMap(int[][] origin, int[][] copied) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copied[i][j] = origin[i][j];
}
}
}
// map 채우기
private static void fill(int[][] map, int row, int col, int d, int val) {
row += dr[d];
col += dc[d];
while (row > -1 && row < N && col > -1 && col < M) {
if (map[row][col] == 6) // cctv는 벽을 통과할 수 없음
break;
// cctv는 cctv를 통과할 수 있음
if (!isCCTV(map[row][col])) {
map[row][col] = val;
}
row += dr[d];
col += dc[d];
}
}
// cctv인지 검사
private static boolean isCCTV(int num) {
if (num > 0 && num < 6) return true;
return false;
}
// 사각지대 계산
private static int getBlind(int[][] map) {
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0)
cnt++;
}
}
return cnt;
}
}
메모리 : 28868KB, 시간 : 280ms
https://www.acmicpc.net/problem/1043
union-find 알고리즘을 사용했다.
처음에는 입력을 받으면서 파티에 진실을 아는 사람이 있다면 Set에 추가하는 방법으로 구현했는데, 그러면 나중 파티에서 진실을 아는 사람을 만날 경우를 계산하지 못했다..
풀이 방법
1. 같은 파티에 간 사람들끼리 모두 union한다.
2. 파티에 있는 사람 중 진실을 아는 사람과 같은 집합에 있는 사람이 없으면 거짓말을 할 수 있다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int[] parents, truth;
static int truthNum;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
int N = Integer.parseInt(stk.nextToken());
int M = Integer.parseInt(stk.nextToken());
// union-find를 위한 parents 배열 초기화
parents = new int[N+1];
for (int i = 1; i <= N; i++) {
makeSet(i);
}
// 진실을 아는 사람 입력
stk = new StringTokenizer(br.readLine());
truthNum = Integer.parseInt(stk.nextToken());
// 진실을 아는 사람이 없으면 모든 파티에서 거짓말할 수 있음
if (truthNum == 0) {
System.out.println(M);
System.exit(0);
}
truth = new int[truthNum];
for (int i = 0; i < truthNum; i++) {
truth[i] = Integer.parseInt(stk.nextToken());
// 진실을 아는 사람끼리 union
if (i > 0) union(truth[i-1], truth[i]);
}
// 파티 입력
int size;
ArrayList<Integer>[] party = new ArrayList[M];
for (int p = 0; p < M; p++) {
stk = new StringTokenizer(br.readLine());
size = Integer.parseInt(stk.nextToken()); // 파티에 온 사람의 수
party[p] = new ArrayList<>();
for (int i = 0; i < size; i++) {
party[p].add(Integer.parseInt(stk.nextToken()));
// 파티에 온 사람끼리 모두 union
if (i > 0) union(party[p].get(i-1), party[p].get(i));
}
}
int answer = 0;
for (ArrayList<Integer> p : party) {
// 파티에서 거짓말을 할 수 있는지 검사
if (canLie(p)) answer++;
}
System.out.println(answer);
}
private static boolean canLie(ArrayList<Integer> p) {
for (int n : p) {
// 진실을 알고 있는 사람과 같은 집합에 있다면 거짓말할 수 없음
// 모두 union했으므로 진실을 알고있는 0번째 사람을 기준으로 검사
if(findSet(truth[0]) == findSet(n)) return false;
}
return true;
}
private static void union(int u, int v) {
parents[findSet(u)] = findSet(v);
}
private static int findSet(int v) {
if (parents[v] == v) return v;
return parents[v] = findSet(parents[v]);
}
private static void makeSet(int v) {
parents[v] = v;
}
}
메모리 : 16128KB, 시간 : 164ms
https://www.acmicpc.net/problem/9935
다른 사람 코드를 참고해서 풀었다.
문자열을 앞부터 차례로 stack에 넣고, 맨 위 문자열이 폭발 문자열이면 pop한다.
이 과정을 반복하면 모든 폭발 문자열을 없앨 수 있다!!
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
static int bomblen;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine(); // 문자열
String bomb = br.readLine(); // 폭발 문자열
bomblen = bomb.length(); // 폭발 문자열 길이
Stack<Character> stack = new Stack<>();
for (int i = 0; i < str.length(); i++) {
// 차례로 stack에 넣음
stack.add(str.charAt(i));
// stack의 크기가 폭발 문자열 길이 이상이라면 폭발 문자열 검사
if (stack.size() >= bomblen) {
// 폭발 문자열이면 모두 pop
if (check(stack, bomb)) {
for (int j = 0; j < bomblen; j++) {
stack.pop();
}
}
}
}
// 남은 문자열이 없으면 FRULA 출력
if (stack.size() == 0) System.out.println("FRULA");
else { // 남은 문자열 출력
StringBuilder sb = new StringBuilder();
for (char c : stack) {
sb.append(c);
}
System.out.println(sb.toString());
}
}
// stack의 top 문자열이 폭발 문자열과 같은지 검사
private static boolean check(Stack<Character> stack, String bomb) {
for (int i = 0; i < bomblen; i++) {
if (stack.get(stack.size() - bomblen + i) != bomb.charAt(i)) return false;
}
return true;
}
}
메모리 : 33768KB, 시간 : 476ms