문제 포인트는 1. 3개의 벽을 세울 수 있는 모든 경우의 수를 구해서 새롭게 복사한 COPY_MAP을 각각 만드는 것 여기서 세울 수 있는 경우의 수가 엄청 많은데 이를 하나하나 다 BFS를 돌려봐야 한다. 2. 1번에서 새운 MAP 에서 BFS 돌려서 안전거리의 영역을 카운트해서 그 안전거리의 최대값을 출력
DFS와 BFS 를 동시에 연습할수 있는 아주 좋은 문제였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] map;
static int[] dy = {1, 0, -1, 0};
static int[] dx = {0, 1, 0, -1};
static int ans = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
DFS(0);
System.out.println(ans);
}
public static void DFS(int cnt) {
if (cnt == 3) {
BFS();
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
map[i][j] = 1;
DFS(cnt + 1);
map[i][j] = 0;
}
}
}
}
public static void BFS() {
// 벽을 새로 새울떄마다 배열 초기화
int[][] copy_map = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copy_map[i][j] = map[i][j];
}
}
Queue<Node> qu = new LinkedList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copy_map[i][j] == 2) {
qu.add(new Node(i, j));
}
}
}
while (!qu.isEmpty()) {
Node curNode = qu.poll();
for (int i = 0; i < 4; i++) {
int ny = curNode.y + dy[i];
int nx = curNode.x + dx[i];
if (ny < 0 || nx < 0 || N <= ny || M <= nx) continue;
if (copy_map[ny][nx] == 0) {
copy_map[ny][nx] = 2;
qu.add(new Node(ny, nx));
}
}
}
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (copy_map[i][j] == 0) {
cnt++;
}
}
}
ans = Math.max(cnt, ans);
}
public static class Node {
int y;
int x;
public Node(int y, int x) {
this.y = y;
this.x = x;
}
}
}
테트리스의 모양처럼 생긴 블록들이 알고보면 DFS의 방향대로 탐색할때의 모양이라는 것을 알아낼 수 있었다. DFS를 visited배열을 true 해주면서 depth가 4일때까지 돌리고 빠져나오면서 visited 배열을 false 해주는 백트래킹 방식으로 구현하였다.
여기서 핵심인 부분은 'ㅏ,ㅗ,ㅜ,ㅓ' 에 대한 블록을 어떻게 처리해줄까였는데 나는 cnt == 2 일때 arr[ny][nx] 의 값을 더해준 뒤 다른 ny,nx가 아닌 다른 방향으로 DFS를 한번 더 돌려서 sum 값을 계산하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] arr;
static boolean[][] visited;
static int[] dy = {1, -1, 0, 0};
static int[] dx = {0, 0, 1, -1};
static int ans = Integer.MIN_VALUE;
public static void main(String[] agrs) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = true;
DFS(i, j, 0, 0);
visited[i][j] = false;
}
}
System.out.println(ans);
}
public static void DFS(int y, int x, int sum, int cnt) {
if (cnt == 4) {
ans = Math.max(sum, ans);
return;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || N <= ny || M <= nx)
continue;
if (visited[ny][nx])
continue;
if (cnt == 2) {
visited[ny][nx] = true;
DFS(y, x, sum + arr[ny][nx], cnt + 1);
visited[ny][nx] = false;
}
visited[ny][nx] = true;
DFS(ny, nx, sum + arr[ny][nx], cnt + 1);
visited[ny][nx] = false;
}
}
}
BFS로 모든 경로를 다 찾으려고 하면 당연히 시간초과가 나버린다. 집에서 치킨집의 조합의 경우의 수 만큼 거리를 백트래킹으로 구하여 그것의 최소값을 구하면 된다. (이 아이디어를 생각해내는데 꽤 오래걸렸다..)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[][] arr;
static boolean[] visited;
static ArrayList<Node> chickenList = new ArrayList<>();
static ArrayList<Node> houseList = new ArrayList<>();
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N + 1][N + 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (arr[i][j] == 1)
houseList.add(new Node(i, j));
if (arr[i][j] == 2)
chickenList.add(new Node(i, j));
}
}
visited = new boolean[chickenList.size()];
DFS(0, 0);
System.out.println(answer);
}
public static void DFS(int idx, int cnt) {
if (cnt == M) {
int res = 0;
for (int i = 0; i < houseList.size(); i++) {
int sum = Integer.MAX_VALUE;
for (int j = 0; j < chickenList.size(); j++) {
if (visited[j]) {
// 각 치킨집에서 집까지의 거리의 최소값
int distance = Math.abs(chickenList.get(j).y - houseList.get(i).y) + Math.abs(chickenList.get(j).x - houseList.get(i).x);
sum = Math.min(sum, distance);
}
}
res += sum;
}
answer = Math.min(answer, res);
return;
}
for (int i = idx; i < chickenList.size(); i++) {
visited[i] = true;
DFS(i + 1, cnt + 1);
visited[i] = false;
}
}
public static class Node {
int x;
int y;
public Node(int y, int x) {
this.x = x;
this.y = y;
}
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static Deque<int[]> qu = new LinkedList<>();
static HashMap<Integer, String> map = new HashMap<>();
static boolean[][] apple;
static int[] dy = {0, 1, 0, -1};
static int[] dx = {1, 0, -1, 0};
static int N, K, L;
static int direction = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
K = Integer.parseInt(br.readLine());
apple = new boolean[101][101];
// 사과 맵
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
apple[y][x] = true;
}
L = Integer.parseInt(br.readLine());
//
for (int i = 0; i < L; i++) {
st = new StringTokenizer(br.readLine());
int X = Integer.parseInt(st.nextToken());
String C = st.nextToken();
map.put(X, C);
}
// 이중 포문 break를 사용하지 않기 위한?
solve();
}
private static void solve() {
int time = 0;
int curY = 1;
int curX = 1;
qu.add(new int[]{1, 1});
while (true) {
int ny = curY + dy[direction];
int nx = curX + dx[direction];
// 맵 범위에 있는지, 몸통이랑 부딪혔는지 확인
if (GameoverCheck(ny, nx))
break;
time++;
qu.add(new int[]{ny, nx});
// 사과가 있으면
if (apple[ny][nx])
apple[ny][nx] = false;
// 사과가 없으면
else {
qu.poll();
}
if (map.containsKey(time)) {
if (map.get(time).equals("D")) {
direction++;
if(direction == 4)
direction = 0;
} else {
direction--;
if(direction == -1)
direction = 3;
}
}
curY = ny;
curX = nx;
}
System.out.println(time + 1);
}
private static boolean GameoverCheck(int ny, int nx) {
boolean flag = false;
// 범위에 벗어나면
if (ny < 1 || nx < 1 || N < ny || N < nx)
flag = true;
// 몸통에 부딪히면
for (int[] arr : qu) {
if (arr[0] == ny && arr[1] == nx) {
flag = true;
break;
}
}
return flag;
}
}
PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.
Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출 해준다.
PriorityQueue는 Heap을 이용하여 구현하는 것이 일반적이다.
데이터를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아 옮기는 방식으로 진행된다. 최대 값이 우선순위인 큐 = 최대 힙, 최소 값이 우선순위인 큐 = 최소 힙
남은 작업량들의 제곱의 합이 야근 지수기 때문에 가장 높은 야근 지수를 N 시간 만큼 -1 해주면 된다. 우선순위큐는 내부적으로 Queue에서 우선순위가 높은 데이터가 먼저 나가기 때문에 poll 할때마다 가장 높은 데이터가 가장 높은 우선순위로 옮겨진다. 이러한 특징을 이용하여 풀면 아래 코드와 같이 구현할 수 있다.
전체 코드
import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
public long solution(int n, int[] works) {
long answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
for (int work : works) {
pq.add(work);
}
while (n > 0) {
int max = pq.poll();
pq.add(--max);
n--;
if(pq.peek() == 0 && n > 0) break;
}
for (Integer num : pq) {
answer += Math.pow(num, 2);
}
if(n != 0) answer = 0;
return answer;
}
}
불량사용자의 조합이 여러가지 나올 수 있기 때문에 중복을 허용하지 않는 set 을 사용하여 불량사용자 조건에 해당되는 user들을 set에 모두 중복, 순서에 상관없이 add 해주는 방법으로 문제를 구현하였다.
유저 아이디(str1)가 불량사용자의 아이디(str2)에 해당이 되는지 검증하여 true/false 로 나타내는 함수이다. 첫번째 if문에서는 길이를 비교하여 길이가 맞지 않으면 false를 return 해주었고, 그아래 코드에선 각 문자를 비교하여 * 이 아니거나 문자열이 일치하지 않는 경우 false를 return 해주었다.
public boolean check(String str1, String str2) {
boolean flag = true;
if (str1.length() != str2.length()) {
flag = false;
return flag;
}
for (int i = 0; i < str1.length(); i++) {
if (str1.charAt(i) != str2.charAt(i) && str2.charAt(i) != '*') {
flag = false;
return flag;
}
}
return flag;
}
여기서 백트래킹 방법으로 HashSet에 다가 해당 되는 userId를 계속 add 해주었다. 유저 수 만큼 for문을 돌려서 해당 유저가 불량 사용자 조건에 해당 되는지를 체크하여 해당된다고 하면 set에 add를 해주었다.
여기서 헷갈렸던 포인트는 DFS(new HashSet<> (set), depth + 1); // 객체 자체를 매개변수로 넘김 DFS(set, depth + 1); // 객체 주소를 매개변수로 넘김
이거에 따라 테스트케이스 3번이 실패하냐 성공하냐로 나뉘었다는 점이었다. 질문하기 게시판에 있는 댓글을 보고 힌트를 얻어 깊은 복사, 얕은 복사 개념 때문이었다는 것을 알게되었고 오늘도 공부할게 정말 많고 갈길이 멀다는 것을 느꼈다.
public void DFS(HashSet<String> set, int depth) {
if (depth == bannedid.length) {
result_set.add(new HashSet<>(set));
return;
}
for (int i = 0; i < userid.length; i++) {
if (set.contains(userid[i]))
continue;
if (check(userid[i], bannedid[depth])) {
set.add(userid[i]);
DFS(new HashSet<> (set), depth + 1);
// DFS(set, depth + 1);
set.remove(userid[i]);
}
}
}
HashSet 안에 HashSet 을 이렇게 선언해준 이유는 불량사용자들의 조합을 Set으로 저장했을 때, 입출력예시 3번 처럼 ["frodo", "fradi", "crodo", "abc123", "frodoc"] ["fr*d*", "*rodo", "******", "******"] 아래 불량유저 조건에 해당되는 조합이 [crodo, abc123, frodo, frodoc] [crodo, abc123, frodo, frodoc] [crodo, abc123, frodo, frodoc] [fradi, abc123, frodo, frodoc] [crodo, abc123, frodo, frodoc] [fradi, abc123, frodo, frodoc] [crodo, abc123, frodo, frodoc] [crodo, fradi, abc123, frodoc] [fradi, abc123, frodo, frodoc] 이런 식으로 5개 나오지만 1,2번과 3,4번은 각각 중복되는 하나의 조합이기 때문에 HashSet에 넣어서 중복을 제거해준 것이다.
HashSet<HashSet<String>> result_set = new HashSet<>();
전체코드
import java.util.*;
class Solution {
static String[] userid;
static String[] bannedid;
static int answer = 0;
HashSet<HashSet<String>> result_set = new HashSet<>();
public int solution(String[] user_id, String[] banned_id) {
userid = user_id;
bannedid = banned_id;
DFS(new HashSet<String>(), 0);
return result_set.size();
}
public void DFS(HashSet<String> set, int depth) {
if (depth == bannedid.length) {
result_set.add(new HashSet<>(set));
return;
}
for (int i = 0; i < userid.length; i++) {
if (set.contains(userid[i]))
continue;
if (check(userid[i], bannedid[depth])) {
set.add(userid[i]);
// new HashSet<> (set) 차이가 뭐지
DFS(new HashSet<> (set), depth + 1);
// DFS(new HashSet<> (), depth + 1);
set.remove(userid[i]);
}
}
}
public boolean check(String str1, String str2) {
boolean flag = true;
if (str1.length() != str2.length()) {
flag = false;
return flag;
}
for (int i = 0; i < str1.length(); i++) {
if (str1.charAt(i) != str2.charAt(i) && str2.charAt(i) != '*') {
flag = false;
return flag;
}
}
return flag;
}
}
Cloneable 인터페이스는 복제해도 되는 클래스임을 명시하는 용도의 믹스인 인터페이스지만, 아쉽게도 의도한 목적을 제대로 이루지 못했다. 여기서 큰 문제점은 clone 메서드가 선언된 곳이 Cloneable이 아닌 OBject이고, 그 마저도 protected이다. 그래서 Cloneable을 구현하는 것만으로는 외부 객체에서 clone 메소드를 호출할 수 없다. 리플렉션을 사용하면 가능하지만, 100% 성공하는 것도 아니다.
이러한 여러 문제점을 가진 인터페이스이지만, Cloneable 방식은 널리 쓰이고 있어서 잘 알아두는 것이 좋다.
Cloneable이 몰고 온 모든 문제를 되짚어봤을 때, 새로운 인터페이스를 만들 때는 절대 Cloneable을 확장해서는 안 되며, 새로운 클래스도 이를 구현해서는 안된다. final 클래스라면 Cloneable을 구현해도 위험이 크지는 않지만, 성능 최적화 관점에서 검토한 후 별다른 문제가 없을 때만 드물게 허용해야 한다.
기본 원칙은 '복제 기능은 생성자와 팩터리를 이용하는게 최고' 라는 것이다.
단, 배열만은 clone 메소드 방식이 가장 깔끔한, 이 규칙의 합당한 예외라 할 수 있다.
public class CopyObject {
private String name;
private int age;
public CopyObject() {
}
/* 복사 생성자 */
public CopyObject(CopyObject original) {
this.name = original.name;
this.age = original.age;
}
/* 복사 팩터리 */
public static CopyObject copy(CopyObject original) {
CopyObject copy = new CopyObject();
copy.name = original.name;
copy.age = original.age;
return copy;
}
public CopyObject(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
@Test
void shallowCopy() {
CopyObject original = new CopyObject("JuHyun", 20);
CopyObject copyConstructor = new CopyObject(original);
CopyObject copyFactory = CopyObject.copy(original);
copyConstructor.setName("JuBal");
copyFactory.setName("BalJu");
System.out.println(original.getName());
System.out.println(copyConstructor.getName());
System.out.println(copyFactory.getName());
}
복사 생성자와 복사 팩터리를 통해 객체를 복사하는 과정도 깊은 복사임을 알 수 있습니다.
깊은 복사를 그림으로 나타내면 다음과 같습니다.
얕은 복사와는 다르게 Heap 영역에 새로운 메모리 공간을 생성하여 실제 값을 복사합니다.
Collections나 Map의 경우 이미 복사 팩터리인 copy() 메소드를 구현하고 있습니다.
/**
* Copies all of the elements from one list into another. After the
* operation, the index of each copied element in the destination list
* will be identical to its index in the source list. The destination
* list's size must be greater than or equal to the source list's size.
* If it is greater, the remaining elements in the destination list are
* unaffected. <p>
*
* This method runs in linear time.
*
* @param <T> the class of the objects in the lists
* @param dest The destination list.
* @param src The source list.
* @throws IndexOutOfBoundsException if the destination list is too small
* to contain the entire source List.
* @throws UnsupportedOperationException if the destination list's
* list-iterator does not support the {@code set} operation.
*/
public static <T> void copy(List<? super T> dest, List<? extends T> src) {
int srcSize = src.size();
if (srcSize > dest.size())
throw new IndexOutOfBoundsException("Source does not fit in dest");
if (srcSize < COPY_THRESHOLD ||
(src instanceof RandomAccess && dest instanceof RandomAccess)) {
for (int i=0; i<srcSize; i++)
dest.set(i, src.get(i));
} else {
ListIterator<? super T> di=dest.listIterator();
ListIterator<? extends T> si=src.listIterator();
for (int i=0; i<srcSize; i++) {
di.next();
di.set(si.next());
}
}
}
