Notice
Recent Posts
천천히 빛나는
삼성 기출 : Week 1 (Java) 본문
Day 1에서는 [연구소, 연산자 끼워넣기, 감시, 스타트와 링크, 치킨배달, 톱니바퀴, 인구이동, 퇴사]를 다룹니다.
14502. (골드4) 연구소
import java.io.*;
import java.util.*;
class Pair{
int first;
int second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
public int first() {
return first;
}
public int second() {
return second;
}
}
public class Main {
static int N, M;
static int[][] map = new int[8][8];
static final int[] dx = {-1, 1, 0, 0};
static final int[] dy = {0, 0, -1, 1};
static List <Pair> list = new ArrayList<>();
static boolean[][] visited = new boolean[8][8];
static int ans;
static void makeWall(int x) {
if(list.size() == 3) {
for(int i = 0; i < list.size(); i++) {
int first = list.get(i).first();
int second = list.get(i).second();
map[first][second] = 1;
}
goVirus();
for(int i = 0; i < list.size(); i++) {
int first = list.get(i).first();
int second = list.get(i).second();
map[first][second] = 0;
}
return;
}
for(int i = x; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 0 && !visited[i][j]) {
visited[i][j] = true;
Pair p = new Pair(i, j);
list.add(p);
makeWall(i);
list.remove(p);
visited[i][j] = false;
}
}
}
}
static void goVirus() {
int[][] orginMap = new int[N][M];
for(int i = 0; i< N; i++) {
for(int j = 0; j< M; j++) {
orginMap[i][j] = map[i][j];
}
}
for(int t = 0; t < 10; t++) {
for(int x = 0; x < N ; x++) {
for(int y = 0; y < M ; y++) {
if(map[x][y] != 2) // 전파 시점
continue;
for(int n = 0; n < 4; n++) {
int nx = x + dx[n];
int ny = y + dy[n];
if(nx < 0 || nx >= N || ny < 0 || ny >= M)
continue;
if(map[nx][ny] == 0) {
map[nx][ny] = 2; // 바이러스 전파
}
}
}
}
}
countSafezone();
for(int i = 0; i< N; i++) {
for(int j = 0; j< M; j++) {
map[i][j] = orginMap[i][j];
}
}
}
static void countSafezone() {
int cnt = 0;
for(int i = 0; i< N; i++) {
for(int j = 0; j< M; j++) {
if(map[i][j] == 0) {
cnt++;
}
}
}
ans = Math.max(ans, cnt);
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 0은 빈칸, 1은 벽, 2는 바이러스
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());
}
}
makeWall(0);
sb.append(ans);
System.out.println(sb.toString());
}
}완전탐색을 이용해서 벽을 세울 곳 3개를 지정하고 connected component를 찾는 코드를 작성하였다.
문제점
1. visited 배열을 따로 만들어서 검색을 해주었는데, map[i][j]만을 이용해서도 충분히 구현할 수 있는 문제였다.
public static void dfs(int wallCnt) {
if(wallCnt == 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(wallCnt+1);
map[i][j] = 0;
}
}
}
}다른분께서 구현한 코드인데 나중에 벽으로 만든 곳 찾아서 검사하는게 아니라 바로 map으로 바꾸면 번거로운 과정을 하지 않아도 된다. 그럼 Pair 형 list 배열도 필요가 없어진다. (벽 고르기 부분에서만 말하는 것입니다.)
달랐던 부분
1. 나는 connected component를 dfs로 찾았는데, bfs로 구현한 분들이 더 많았다.
import java.util.Queue;
public static Queue<virus> queue = new LinkedList<virus>();
while (!queue.isEmpty()){
virus v = queue.poll();
for(int i=0; i<4; i++) {
int nx = v.x + dx[i];
int ny = v.y + dy[i];
if(0 <= nx && nx <N && 0<= ny && ny <M) {
if(copyMap[nx][ny] == 0) {
copyMap[nx][ny] = 2;
queue.add(new virus(nx, ny));
}
}
}
}
funcSafeZone(copyMap);
}다른 분께서 bfs로 connected component를 찾는 코드를 작성해주셨길래 가져왔다! 여기서 virus는 내가 만든 pair 클래스랑 똑같이 구현된 코드이다. (static 인거 빼고만)
https://shine-slowly.tistory.com/49
알고리즘 : DFS와 BFS (2) - BFS (C++로 구현)
https://shine-slowly.tistory.com/48 알고리즘 : DFS와 BFS (1) - DFS (C++로 구현) 참고 영상 : https://youtu.be/7C9RgOcvkvo?si=PuM-7RIBWbVPtYTw bfs와 dfs는 탐색 알고리즘이다. 내가 헷갈렸던 부분이 있는데 그래프를 인접
shine-slowly.tistory.com
copy된 배열에서 바이러스를 전파시키고 (2를 대입) 0이 아닌 값을 count 해주는 부분은 똑같다.
다른 부분은 크게 없는 것 같지만 자바의 queue 사용법을 배워야겠다는 생각을 했다. dueque의 ArrayList로도 할 수 있다고 들었으니 둘다 해봐야지! (자료구조 공부를 좀 해보자)
14888. (실버1) 연산자 끼워넣기
import java.util.*;
import java.io.*;
public class Main {
static int N;
// 0: 덧셈, 1: 뺄셈, 2: 곱셈, 3: 나누기
static int[] num = new int [100];
static int[] operand = new int[4];
static List <Integer> list = new ArrayList<>();
static int max = -1_000_000_000;
static int min = 1_000_000_000;
static void findMaxVal(int idx) {
if(list.size() >= N-1) {
int temp = num[0];
for(int i = 0; i < N-1; i++) {
int op = list.get(i);
if(op == 0) {
temp += num[i+1];
}else if (op == 1) {
temp -= num[i+1];
}else if (op == 2) {
temp *= num[i+1];
}else {
temp /= num[i+1];
}
}
max = Math.max(max, temp);
min = Math.min(min, temp);
}
if(operand[0]!=0) {
operand[0]--;
list.add(0);
findMaxVal(idx+1);
list.remove(list.size() - 1);
operand[0]++;
}
if(operand[1]!=0) {
operand[1]--;
list.add(1);
findMaxVal(idx+1);
list.remove(list.size() - 1);
operand[1]++;
}
if(operand[2]!=0) {
operand[2]--;
list.add(2);
findMaxVal(idx+1);
list.remove(list.size() - 1);
operand[2]++;
}
if(operand[3]!=0) {
operand[3]--;
list.add(3);
findMaxVal(idx+1);
list.remove(list.size() - 1);
operand[3]++;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuffer sb = new StringBuffer();
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<N; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine(), " ");
for(int i=0; i<4; i++) {
operand[i] = Integer.parseInt(st.nextToken());
}
findMaxVal(0);
sb.append(max).append("\n").append(min);
System.out.println(sb.toString());
}
}연산자의 개수만큼 완전탐색을 하여 모든 경우의 수를 탐색하는 코드이다.
문제점
1. c++로 풀던 습관이 남아있어서 List를 굉장히 많이 쓰게 되는데, 크기가 N인 배열을 만들고 카운트는 매개변수를 통해 구현하는 것이 훨씬 좋을 것 같았다. 자바는 list가 아니라 배열을 쓰는 것이 시작을 훨씬 단축시키고 좋다는 것을 잊지 말자.
public static void dfs(int num, int idx) {
if (idx == N) {
MAX = Math.max(MAX, num);
MIN = Math.min(MIN, num);
return;
}
for (int i = 0; i < 4; i++) {
if (operator[i] > 0) {
operator[i]--;
switch (i) {
case 0: dfs(num + number[idx], idx + 1); break;
case 1: dfs(num - number[idx], idx + 1); break;
case 2: dfs(num * number[idx], idx + 1); break;
case 3: dfs(num / number[idx], idx + 1); break;
}
operator[i]++;
}
}
}여기서도 number을 사용하는 것을 알 수 있다. ArrayList가 아니다
15683. (골드4) 감시
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int M;
static int [][] map = new int[8][8];
static Pair [] cctv = new Pair[8];
static int cctvNum;
static boolean[][] visited = new boolean[8][8];
static int dx [] = {-1, 0, 1, 0};
static int dy [] = {0, 1, 0, -1};
static int ans = 64;
static class Pair{
int first;
int second;
int first() {
return first;
}
int second() {
return second;
}
}
static void detect(int x, int y, int dir) {
if(map[x][y] == 6) // 벽
return;
if(map[x][y] == 0 )
visited[x][y] = true;
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx < 0 || nx >= N || ny < 0 || ny >= M)
return;
detect(nx, ny, dir);
}
static int countArea() {
int cnt = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 6)
continue;
if(visited[i][j]==false)
cnt++;
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
visited[i][j] = false;
}
}
return cnt - cctvNum > 0 ? cnt - cctvNum : 0;
}
static void cctv_Solution(int numOfCCTV) {
if(numOfCCTV >= cctvNum) {
int temp = countArea();
ans = Math.min(ans, temp);
return;
}
int x = cctv[numOfCCTV].first();
int y = cctv[numOfCCTV].second();
for(int d = 0; d < 4; d++) {
boolean temp [][] = new boolean[8][8];
for(int i = 0; i<N; i++) {
for(int j = 0; j< M; j++) {
temp[i][j] = visited[i][j];
}
}
if(map[x][y] == 1) {
detect(x, y, d); // 네 방향!
}
else if(map[x][y] == 2) {
detect(x, y, d);
detect(x, y, (d+2)%4);
}
else if(map[x][y] == 3) {
detect(x, y, d);
detect(x, y, (d+1)%4);
}
else if(map[x][y] == 4) {
detect(x, y, d);
detect(x, y, (d+1)%4);
detect(x, y, (d+2)%4);
}
else if(map[x][y] == 5) {
detect(x, y, d);
detect(x, y, d+1);
detect(x, y, d+2);
detect(x, y, d+3);
}
// 탐색하고 돌아왔음
cctv_Solution(numOfCCTV+1);
for(int i = 0; i<N; i++) {
for(int j = 0; j< M; j++) {
visited[i][j] = temp[i][j];
}
}
if(map[x][y] == 5)
break;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int j = 0;
while(st.hasMoreTokens()) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] > 0 && map[i][j] < 6) {
cctv[cctvNum] = new Pair();
cctv[cctvNum].first = i;
cctv[cctvNum].second = j;
cctvNum++;
}
j++;
}
}
cctv_Solution(0);
sb.append(ans);
System.out.println(sb.toString());
}
}1번 cctv의 경우 90도 회전할 경우 4개의 다른 경우의 수가 나오고, 5번 cctv의 경우 90도를 회전해도 동일한 기능을 하게 된다. 하지만 위 코드에서는 90도 회전할 경우 다른 경우의 수가 나온다고 생각하고 코드를 작성하였다. (5번 제외)
내가 예전에 이해하려고 적어둔 그래프이다.
다른점
나는 detect에서 배열 하나를 복사해서 다시 돌려주는 작업을 반복하는데, 매개변수를 통해서 배열을 전달해주는 경우도 있었다.
public static void watch(CCTV cctv, int d) {
Queue<CCTV> queue = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
queue.add(cctv);
visited[cctv.x][cctv.y] = true;
while(!queue.isEmpty()) {
int nx = queue.peek().x + dx[d];
int ny = queue.poll().y + dy[d];
if(nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] == 6) { // 범위를 벗어나거나 벽을 만나면 끝
break;
}
if(copyMap[nx][ny] == 0) {
copyMap[nx][ny] = -1; // 빈칸이라면 감시할 수 있다는 의미로 -1
queue.add(new CCTV(cctv.num, nx, ny));
} else { // 다른 cctv가 있거나 이미 감시된 칸이라면
queue.add(new CCTV(cctv.num, nx, ny)); // 그냥 통과
}
}
}또한 bfs로도 탐색은 진행할 수 있다!
14889. (실버1) 스타트와 링크
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int[][] map = new int[20][20];
static List<Integer> list = new ArrayList<>();
static int ans = Integer.MAX_VALUE;
static void makingGroup(int idx) {
if(list.size()==N/2) {
int startAns = 0;
int linkAns = 0;
boolean[] tempArr = new boolean[20];
for(int i = 0; i< list.size(); i++) {
int tempA = list.get(i);
tempArr[tempA] = true;
for(int j = 0; j< list.size(); j++) {
int tempB = list.get(j);
if(tempA != tempB) {
startAns += map[tempA][tempB];
}
}
}
for(int i = 0; i< N; i++) {
if(tempArr[i] == false) {
for(int j = 0; j < N; j++) {
if(tempArr[j] == false && i!=j) {
linkAns += map[i][j];
}
}
}
}
ans = Math.min(ans, Math.abs(linkAns-startAns));
return;
}
for(int i = idx; i< N; i++) {
list.add(i);
makingGroup(i+1);
list.remove((Integer)i);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
for(int i = 0; i<N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int j = 0;
while(st.hasMoreTokens()) {
map[i][j++] = Integer.parseInt(st.nextToken());
}
}
makingGroup(0);
sb.append(ans);
System.out.println(sb.toString());
}
}조합으로 반을 뽑고 이중 for문을 통해서 점수를 더해주도록 구현하였다.
문제점
1. list를 만들 필요 없이 visited만으로도 확인할 수 있는 문제였다. 방문 했으면 당연히 list 안에 들어있고, 아니라면 false일 것이다. 그 이후는 이중 for문으로 구현하는 것이 맞다.
public static void diff() {
int start = 0;
int link = 0;
for(int i = 0 ; i < N-1 ; i++) {
for(int j = i+1 ; j < N ; j++) {
if(visit[i]==true && visit[j]==true) {
start += arr[i][j];
start += arr[j][i];
}
else if(visit[i]==false && visit[j]==false) {
link += arr[i][j];
link += arr[j][i];
}
}
}
int val = Math.abs(start - link);
if(val == 0) {
System.out.println(val);
System.exit(0);
}
min=Math.min(min,val);
}visited만으로 해결하는 것을 볼 수 있다.
15686. (골드5) 치킨 배달
import java.io.*;
import java.util.*;
class Pair{
int first;
int second;
Pair(int first, int second){
this.first = first;
this.second = second;
}
int first() {
return first;
}
int second() {
return second;
}
}
public class Main {
static int[][] map = new int[50][50];
static List<Integer> chicken = new ArrayList<>();
static List<Pair> list = new ArrayList<>();
static int N;
static int M;
static int ans = Integer.MAX_VALUE;
static void findShort(int idx) {
if(chicken.size() >= M) {
int tempAns = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(map[i][j]==1) {
int temp = Integer.MAX_VALUE;
for(int k = 0; k < chicken.size(); k++) {
int idx_c = chicken.get(k);
int nx = Math.abs(i - list.get(idx_c).first());
int ny = Math.abs(j - list.get(idx_c).second());
temp = Math.min(temp, nx + ny);
}
tempAns += temp;
}
}
}
ans = Math.min(ans, tempAns);
return;
}
for(int i = idx; i < list.size(); i++) {
chicken.add(i);
findShort(i+1);
chicken.remove((Integer)i);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int j = 0;
while(st.hasMoreTokens()) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == 2) {
list.add(new Pair(i, j));
}
j++;
}
}
findShort(0);
sb.append(ans);
System.out.println(sb.toString());
}
}치킨집 3개를 조합으로 정하고 치킨거리를 직접 계산하는 코드이다. 사용자 정의 클래스를 받도록 하려면 (위에 나왔던 virus처럼) List를 사용해야 하는 것 같았다.
치킨집 m개를 뽑고 모든 치킨집까지의 거리 중 최소를 찾아 더해주었다.
14891. (골드5) 톱니바퀴
import java.io.*;
import java.util.*;
public class Main {
static LinkedList<Integer>[] dq = new LinkedList[4];
static void turningSN(int num, int dir) {
int[] tempTwo = new int[4];
int[] tempSix = new int[4];
for(int i = 0; i < 4; i++) {
tempTwo[i] = dq[i].get(2);
tempSix[i] = dq[i].get(6);
}
if(dir == 1) {
int temp = dq[num].get(7);
dq[num].remove(7);
dq[num].addFirst(temp);
}else {
int temp = dq[num].get(0);
dq[num].remove(0);
dq[num].addLast(temp);
}
int leftDir = dir;
for(int i = num - 1; i >= 0; i--) {
leftDir = (leftDir == 1) ? -1 : 1;
if(tempSix[i+1] == tempTwo[i])
break;
if(leftDir == 1) {
int temp = dq[i].get(7);
dq[i].remove(7);
dq[i].addFirst(temp);
}else {
int temp = dq[i].get(0);
dq[i].remove(0);
dq[i].addLast(temp);
}
}
int rigthDir = dir;
for(int i = num + 1; i < 4; i++) {
rigthDir = (rigthDir == 1) ? -1 : 1;
if(tempTwo[i-1] == tempSix[i])
break;
if(rigthDir == 1) {
int temp = dq[i].get(7);
dq[i].remove(7);
dq[i].addFirst(temp);
}else {
int temp = dq[i].get(0);
dq[i].remove(0);
dq[i].addLast(temp);
}
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
for(int i = 0; i < 4; i++) {
String turn = br.readLine();
dq[i] = new LinkedList<>();
for(int j = 0; j < turn.length(); j++) {
dq[i].add((Integer)(turn.charAt(j) - '0'));
}
}
int test = Integer.parseInt(br.readLine());
for(int i = 0; i < test; i++) {
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
turningSN(num-1, dir); // 1이 시계 -1이 반시계
}
int total = 0;
for(int i = 0; i <4; i++) {
if(dq[i].get(0) == 1) {
total += Math.pow(2, i);
}
}
sb.append(total);
System.out.println(sb.toString());
}
}자바로 덱을 어떻게 구현해야하고 덱에서도 인덱스를 통한 접근이 가능한지를 몰라서 ArrayList로 풀었다. c++에서는 가능했던 부분이라 일단 대충 짜긴했지만 맞는 코드인지 의구심이 엄청 들었다.
다른점
1. 일단 자바는 덱을 통한 인덱스 접근이 되지 않는다... 그래서 대부분 인덱스 접근이 필요하면 배열로 구현해서 직접 swap 코드로 만들어서 회전 기능들을 만드셨다.
https://jisunshine.tistory.com/77
위 코드가 보편적인 코드였다.
https://velog.io/@qwerty1434/%EB%B0%B1%EC%A4%80-14891%EB%B2%88-%ED%86%B1%EB%8B%88%EB%B0%94%ED%80%B4
나랑 비슷하게 생각하신 분이 있으시길래 이 링크도 첨부하였다.
16234. (골드4) 인구 이동
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int L;
static int R;
static int [][]map = new int[50][50];
static int [][]tempMap = new int[50][50];
static boolean [][]visited = new boolean[50][50];
static List<Pair>list = new ArrayList<>();
static final int[] dx = {-1, 0, 1, 0};
static final int[] dy = {0, 1, 0, -1};
static int total;
static int cnt;
static class Pair{
int first, second;
Pair(int first, int second){
this.first = first;
this.second = second;
}
}
static void openCastle(int x, int y) {
visited[x][y] = true;
list.add(new Pair(x, y));
total += map[x][y];
cnt++;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= N || ny < 0 || ny >= N)
continue;
if(visited[nx][ny] == false) {
int diff = Math.abs(map[nx][ny] - map[x][y]);
if(diff >= L && diff <= R)
openCastle(nx, ny);
}
}
}
static void makingSame() {
int average = total / cnt;
for(int i = 0; i < list.size(); i++) {
int x = list.get(i).first;
int y = list.get(i).second;
tempMap[x][y] = average;
}
}
static void reset() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
visited[i][j] = false;
}
}
total = 0;
cnt = 0;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
boolean flag = true;
int day = 0;
while(flag) {
flag = false;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
tempMap[i][j] = map[i][j];
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(visited[i][j] == false) {
cnt = 0;
total = 0;
openCastle(i, j);
if(cnt > 1) {
flag = true;
makingSame();
}
list.clear();
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
map[i][j] = tempMap[i][j];
}
}
if(flag)
day++;
reset();
}
sb.append(day);
System.out.println(sb.toString());
}
}시작점에서 사방으로 퍼져나가서 닿을 수 있는 부분을 찾는다. 시작점에서 직접 접근하지 못하더라도 근처에 있는 나라에서 접근할 수 있다면 연합을 할 수 있다. 근처에 한번도 가지 않았고 국가 간 차이도 범위 안에 들어온다면 visited를 변경한다.
만약 cnt가 1 이상, 즉 하나의 connected component로 분류된 구역에 국가가 둘 이상 존재한다면 flag를 true로 만들어 주고 day가 하나 지났다고 해주었다.
makingSame 함수를 통해 인구차이가 없도록 통일시켜주는 (tempMap에 일단 저장을 해서 다른 곳에서 connected component가 있는지 확인을 하고 합치는 과정을 진행) 과정을 반복하였다.
내 주언어가 c++이고 최근에 자바를 배우고 다시 풀기 시작한 것이라서 최대값으로 배열을 자꾸 설정해주는 버릇이 있는데 자바에서는 굳이 그럴 필요가 없다고 한다.
다른점
1. 국경선 확인을 할 때 bfs로도 풀 수가 있다. (Deque을 이용해서 bfs를 구현해볼 예정이다!)
static void bfs(int r, int c) {
Deque<Pair> q= new ArrayDeque<>();
q.offer(new Pair(r, c));
int sum = 0;
visited[r][c] = true;
while(!q.isEmpty()) {
int x = q.peek().first;
int y = q.peek().second;
q.poll();
sum += map[x][y];
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if(visited[nx][ny] == true) continue;
q.offer(new Pair(nx, ny));
visited[nx][ny] = true;
}
}
}Deque에 대해서 여기선 자세히 다르지 않겠지만 이와 같이 Deque을 이용해서 bfs를 구현할 수 있다.
14501. (실버3) 퇴사
import java.io.*;
import java.util.*;
public class Main {
static int[] T;
static int[] P;
static int[] dpTable; // 직전까지의 최적의 해
static int ans;
static int N;
static void findMax() {
for (int i = 0; i < N; i++)
{
int idx = i + T[i];
if(idx == N) {
if(i > 0 && dpTable[i] < dpTable[i-1])
dpTable[i] = dpTable[i-1];
ans = Math.max(ans, dpTable[i] + P[i]);
continue;
}
if(idx > N) {
ans = Math.max(ans, dpTable[i]);
continue;
}
if(i > 0 && dpTable[i] < dpTable[i-1])
dpTable[i] = dpTable[i-1]; // 전에꺼가 더 나음
dpTable[idx] = Math.max(P[i]+dpTable[i], dpTable[idx]);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st= null;
N = Integer.parseInt(br.readLine());
T = new int[N];
P = new int[N];
dpTable = new int[N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
T[i]= Integer.parseInt(st.nextToken());
P[i]= Integer.parseInt(st.nextToken());
}
findMax();
sb.append(ans);
System.out.println(sb.toString());
}
}DP 문제인걸 너무 잘 알고 풀어서 (유일한 삼성 기출의 DP문제이기 때문에...) 바로 DP로 접근했던게 아쉬운 부분이었다.
dpTable은 직접까지의 최적의 해를 저장하는 값이다. 보통 dpTable 구현할 때 자기 자신까지의 최적의 해로 했었어서 어떻게 식을 짜야할지 고민을 많이 했다.
dpTable[3일] = Max(dpTable[2일], dpTable[3일])
3일에서는 4일로 바로 접근할 수가 있으므로 dpTable[4일] = Max(dpTable[4일], dpTable[3일] + P[3일]); 을 통해서 3일을 거쳐가는 것이 좋은지, 아니면 그 전에 이미 좋은 값이 나와었는지 검사를 해준다.
문제점
1. 나는 -1로 접근했는데 +1로 접근하고 마지막 값을 가져오는 것이 훨씬 간단하다.
int[] dp = new int[Case+1];
for(int i=0;i<Case;i++) {
if(i+T[i]<=Case) { //범위에 벗어나지 않는다면
dp[i+T[i]]=Math.max(dp[i+T[i]],dp[i]+P[i]);
}
dp[i+1]=Math.max(dp[i+1],dp[i]);
}
System.out.println(dp[Case]);dpTable을 하나 더 크게 만들었다면 max를 따로 만들어주거나 계산하는 과정을 작성하지 않아도 되었다. 다른 분들의 코드를 참고하면서 최대한 간결하게 짜는 연습을 해야겠다.
1주차 삼성 기출 풀이 끝 :D