티스토리 뷰
목차
1. 빙산(2573)
👉 소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] moveX = {0, 0, -1, 1};
static int[] moveY = {-1, 1, 0, 0};
static int year;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int width = 0, heigth = 0, count = 0, iceS = -1;
width = Integer.parseInt(st.nextToken());
heigth = Integer.parseInt(st.nextToken());
int[][] ground = new int[width][heigth];
boolean[][] iceAge; // 녹일 때 당시 방문 체크
// 입력
for(int i = 0; i < width; i++) {
String[] s = br.readLine().split(" ");
for(int j = 0; j < heigth; j++) {
ground[i][j] = Integer.parseInt(s[j]);
}
}
// 빙하 녹이기
while(iceS < 2) {
if(iceS == 0) {
year = 0;
break;
}
year++;
iceAge = new boolean[width][heigth];
for(int i = 0; i < width; i++) {
for(int j = 0; j < heigth; j++) {
// 빙하라면 동서남북으로 바다의 개수를 체크하여 녹인다
if(ground[i][j] != 0) {
iceAge[i][j] = true;
count = dfs(ground, iceAge, i, j, width, heigth, 0);
}
if(ground[i][j] - count >= 0) {
ground[i][j] -= count;
if(ground[i][j] - count == 0) {
}
}else if(ground[i][j] - count <= 0 || ground[i][j] == 0){
ground[i][j] = 0;
}
}
}
// 덩어리가 두개 나오는지 확인
iceS = 0;
iceAge = new boolean[width][heigth];
for(int i = 0; i < width; i++) {
for(int j = 0; j < heigth; j++) {
if(!iceAge[i][j] && ground[i][j] != 0) {
dfsCheck(ground, iceAge, i, j, width, heigth, count);
iceS++;
}
}
}
}
System.out.println(year);
}
public static int dfsCheck(int[][] arr, boolean[][] check, int x, int y, int N, int M, int cnt) {
check[x][y] = true;
for(int i = 0; i < 4; i++) {
int nextX = x + moveX[i];
int nextY = y + moveY[i];
if(nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
if(arr[nextX][nextY] != 0 && !check[nextX][nextY]) {
dfsCheck(arr, check, nextX, nextY, N, M, cnt);
}
}
}
return cnt;
}
public static int dfs(int[][] arr, boolean[][] check, int x, int y, int N, int M, int cnt) {
check[x][y] = true;
cnt = 0;
for(int i = 0; i < 4; i++) {
int nextX = x + moveX[i];
int nextY = y + moveY[i];
if(nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
if(arr[nextX][nextY] == 0 && !check[nextX][nextY]) {
cnt++; // 바다 수 체크
}
if(arr[nextX][nextY] != 0 && !check[nextX][nextY]) {
dfs(arr, check, nextX, nextY, N, M, cnt);
}
}
}
return cnt;
}
}-빙산을 녹여가며 dfs로 풀이했는데 빙하를 녹이는 부분은 금방 구현했으나 탐색하는 부분에서 삽질을 너무 많이 했다,, 생각을 정리하고 짰는데도 짜다보니 내가 짠 코드에 대해 헷갈려 했다. 너~~무 부족한듯
2. 숨바꼭질4(13913)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int subin, sister;
static int[] visited = new int[100001];
static int[] parent = new int[100001];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
subin = Integer.parseInt(st.nextToken());
sister = Integer.parseInt(st.nextToken());
System.out.println(bfs(subin));
int tmp = sister;
Stack<Integer> s = new Stack<Integer>();
while(tmp != subin) {
s.push(tmp);
tmp = parent[tmp];
}
s.push(tmp);
while(!s.isEmpty()) {
System.out.print(s.pop() + " ");
}
br.close();
}
public static int bfs(int start) throws IOException {
Queue<Integer> q = new LinkedList<Integer>();
q.offer(start);
visited[start] = 1;
while(!q.isEmpty()) {
int find = q.poll();
if(find == sister) {
return visited[find] - 1;
}
if(find - 1 >= 0 && visited[find - 1] == 0) {
q.offer(find - 1);
visited[find - 1] = visited[find] + 1;
parent[find - 1] = find;
}
if(find + 1 <= 1000000 && visited[find + 1] == 0) {
q.offer(find + 1);
visited[find + 1] = visited[find] + 1;
parent[find + 1] = find;
}
if(find * 2 <= 100000 && visited[find * 2] == 0) {
q.offer(find * 2);
visited[find * 2] = visited[find] + 1;
parent[find * 2] = find;
}
}
return -1;
}
}- 수빈이가 동생한테 까지 가는 숨바꼭질 문제에서 가는 루트까지 찾아내는 조건이 추가된 문제인데 parent 배열에 각 인덱스에다가 부모의 인덱스를 저장하여 스택에 넣음으로써 해결했다.
3. 연구소(14502)
👉 소스코드
import java.io.*;
import java.util.*;
import java.util.regex.Pattern;
public class Main {
/*
* 14502 연구소
*/
static int N, M, count, result = 0;;
static int[] moveN = {0, 0, -1, 1}, moveM = {-1, 1, 0, 0};
static int[][] arr;
static boolean[][] visited;
static ArrayList<Point> list = new ArrayList<Point>();
public static void main(String[] args) throws Exception {
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++) {
String[] s = br.readLine().split(" ");
for(int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(s[j]);
}
}
dfs(0);
System.out.println(result);
}
// 1을 3개를 넣어보며 안전영역 탐색
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(arr[i][j] == 0) {
arr[i][j] = 1;
dfs(cnt +1);
arr[i][j] = 0;
}
}
}
}
public static void bfs() {
Queue<Point> q = new LinkedList<Point>();
visited[0][0] = true;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(arr[i][j] == 2) {
q.offer(new Point(i, j));
}
}
}
int[][] copyArr = new int[N][M];
for(int i = 0; i < N; i++) {
copyArr[i] = arr[i].clone();
}
while(!q.isEmpty()) {
Point p = q.poll();
for(int j = 0; j < 4; j++) {
int nextX = p.x + moveN[j];
int nextY = p.y + moveM[j];
if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;
if(copyArr[nextX][nextY] == 0) {
copyArr[nextX][nextY] = 2;
q.offer(new Point(nextX, nextY));
}
}
}
int cnt = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(copyArr[i][j] == 0) {
cnt++;
}
}
}
result = Math.max(result, cnt);
}
public static boolean checkVirus(int x, int y) {
if(x < 0 || y < 0 || x >= N | y >= M) return false;
for(int i = 0; i < list.size(); i++) {
Point p = list.get(i);
int checkX = p.x + moveN[i];
int checkY = p.y + moveM[i];
if(checkX < 0 && checkY < 0 && checkX >= N && checkY >= M) return false;
}
return true;
}
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}- dfs 조합을 통해 벽을 3개 세워보면서 bfs로 바이러스를 감염시킨 후, 탐색을 통해 안전영역인 0의 개수를 세어 변수에 저장한 후, 최대값을 갱신해가면서 풀이하는 방법으로 진행하였습니다. 스텝별로 생각해야 될 부분이 있어서 저에게는 쉽지 않았는데요 타인이 풀이한 코드를 참고해 가면서 풀이를 진행했습니다.
4. Tow Dots(16929)
👉 소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, cN, cM;
static char[][] map;
static boolean[][] visited;
static int[] moveN = {0, 0, -1, 1}, moveM = {-1, 1, 0, 0};
public static void main(String[] args) throws Exception {
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 char[N][M];
for(int i = 0; i < N; i++) {
map[i] = br.readLine().toCharArray();
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
visited = new boolean[N][M];
cN = i;
cM = j;
if(dfs(i, j, 1)) {
System.out.println("Yes");
return;
}
}
}
System.out.println("No");
}
public static boolean dfs(int n, int m, int count) {
visited[n][m] = true;
for(int i = 0; i < 4; i++) {
int nextN = n + moveN[i];
int nextM = m + moveM[i];
if(nextN >= 0 && nextM >= 0 && nextN < N && nextM < M && map[n][m] == map[nextN][nextM]) {
if(!visited[nextN][nextM]) {
visited[nextN][nextM] = true;
if(dfs(nextN, nextM, count + 1)) return true;
}else{
if(count >= 4 && nextN == cN && nextM == cM) {
return true;
}
}
}
}
return false;
}
}- 첫번째 지정한 좌표와 같으면서 count를 했을 때 4이면 Yes를 아니면 No를 출력하는 방식으로 진행했다
4. 작업(2056)
👉 소스코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int[] jobTable = new int[N + 1];
int[] jobTime = new int[N + 1];
for (int i = 0; i <= N; i++) {
// 각 인데스에 있는 인접 리스트 초기화
list.add(new ArrayList<Integer>());
}
/*
* 처음에는 두번째줄부터 N + 1번째 줄까지 주어지는 값을 한번에 다 받아서 리스트에 넣었는데
* 블로그 참고하며 각각 따로 받아서 처리하는게 수월하여 로직 변경,,
*/
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
jobTime[i] = Integer.parseInt(st.nextToken());
int count = Integer.parseInt(st.nextToken());
jobTable[i] = count;
for (int j = 0; j < count; j++) {
int num = Integer.parseInt(st.nextToken());
list.get(num).add(i);
}
}
System.out.println(topologicalSort(jobTable, jobTime));
}
public static int topologicalSort(int[] jobTable, int[] jobTime) {
Queue<Integer> q = new LinkedList<Integer>();
// 각 순번의 작업마다 시간을 체크해줄 배열
int[] result = new int[N + 1];
for (int i = 1; i <= N; i++) {
result[i] = jobTime[i];
// 인접한 노드가 없는 노드 먼저 탐색하기 위해 큐에 집어넣음
if (jobTable[i] == 0)
q.offer(i);
}
while (!q.isEmpty()) {
int next = q.poll();
// 큐에서 뽑은 노드와 인접한 노드의 리스트를 가져와서 탐색 시작
for (int x : list.get(next)) {
// 뽑은 노드와 인접해 있는 노드들을 탐색시작한 후 진입차수 차감 (간선 삭제)
jobTable[x]--;
// node가 바라보는 index가 다음 차수에 행해야 할 작업 즉, 다음번에 올 노드인데 최대 값 갱신
// 선행작업이 끝난 후 후행 작업보다 윗도는 작업시간으로 변경
result[x] = Math.max(result[x], result[next]+ jobTime[x]);
// 간선이 제거된 정점을 큐에 넣기
if (jobTable[x] == 0) {
q.offer(x);
}
}
}
Arrays.sort(result);
return result[result.length - 1];
}
}- 처음 위상정렬 문제를 풀어봤는데 문제를 해결하는 과정이 정말 흥미롭다, 이해하는데 시간이 조금 걸렸고 다시 보면 원점이지만 계속해서 문제풀이를 해나간다면 내것으로 만들 수 있는 느낌이 든다.
5. DSLR(9019)
👉 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
for(int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
bfs(a, b);
}
bw.flush();
br.close();
bw.close();
}
public static void bfs(int a, int b) throws IOException {
boolean[] visited = new boolean[10000];
Queue<Cal> q = new LinkedList<Cal>();
q.offer(new Cal(a, ""));
visited[a] = true;
while(!q.isEmpty()) {
Cal c = q.poll();
if(c.num == b) {
bw.write(c.val + "\n");
break;
}
int D = (c.num * 2) % 10000;
int S = c.num == 0 ? 9999 : c.num - 1;
int L = (c.num % 1000) * 10 + c.num / 1000;
int R = (c.num % 10) * 1000 + c.num / 10;
if(!visited[D]) {
q.offer(new Cal(D, c.val + "D"));
visited[D] = true;
}
if(!visited[S]) {
q.offer(new Cal(S, c.val + "S"));
visited[S] = true;
}
if(!visited[L]) {
q.offer(new Cal(L, c.val + "L"));
visited[L] = true;
}
if(!visited[R]) {
q.offer(new Cal(R, c.val + "R"));
visited[R] = true;
}
}
}
static class Cal {
int num;
String val;
public Cal (int num, String val) {
this.num = num;
this.val = val;
}
}
}- 처음에 반복문을 돌려 해결하려다가 계속 시간초과가 나고 L이랑 R을 문자열로 변환한후 잘라가며 해결했는데 이 방법으로는 해결이 안될거 같아 블로그를 참고해가면서 해결했다. 쉬운 편인데 삽질을 너무 많이해서 현타가 온다!!
6. 소수 경로(1963)
👉 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int maxNum = 10000;
static int T;
static boolean[] prime = new boolean[maxNum];
static int[] d = {1000, 100, 10, 1};
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
decCheck(); // 소수 체크에 필요하여 실행
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
for(int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
bfs(a, b);
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static void bfs(int a, int b) throws IOException {
Queue<Integer> q = new LinkedList<Integer>();
q.offer(a);
boolean[] visited = new boolean[maxNum]; // 방문 여부
int[] count = new int[maxNum]; // b까지 가기 위하여 counting
visited[a] = true;
while(!q.isEmpty()) {
int cur = q.poll();
if(cur == b) {
if(!visited[b]) { // b라는 수를 방문한이 없다면 만들 수 없는 수
sb.append("Impossible\n");
}else {
sb.append(count[b] + "\n");
}
return;
}
for(int i = 0; i < 4; i++) {
int value = cur / d[i] / 10; // 4자리 수 중 왼쪽 자리의 수
int mod = cur % d[i]; // 4자리 수 중 오른쪽 자리의 수
for(int j = 0; j <= 9; j++) {
if(i == 0 && j == 0) continue; // 0039 같은 비밀번호는 존재하지 않는다고 하였기 때문에 생략
int next = (value * d[i] * 10) + (j * d[i]) + mod; // 한자리씩 1부터 9까지 반복하며 탐색
if(!visited[next] && !prime[next]) {
q.offer(next);
visited[next] = true;
count[next] = count[cur] + 1;
}
}
}
}
}
public static void decCheck() {
prime[0] = prime[1] = true;
for(int i = 2; i * i < maxNum; i++) {
if(!prime[i]) {
for(int j = i * i; j < maxNum; j += i) prime[j] = true;
}
}
}
}- 다른 부분은 어렵다고 느끼지 못했는데 문제에서 이야기한 한번에 한자리만 바꿀 수 있다는 부분을 구현하는게 어려워서 블로그를 참고해가면서 풀이를 진행했다. 문제에서 주어진 조건에 대하여 바로 바로 아이디어를 떠올리는 부분이 아직은 익숙치 않은듯한 모양이다,, 오늘은 비가 오는 날이라 공부하기 더 좋은날이다! 화이팅!!
7. 이분 그래프(1707)
👉 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int T, V, E;
static ArrayList<ArrayList<Integer>> map;
static int[] colors;
static boolean flag;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
for(int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
map = new ArrayList<>();
flag = true;
for(int k = 0; k <= V; k++) {
map.add(new ArrayList<Integer>());
}
for(int j = 0; j < E; j++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map.get(a).add(b);
map.get(b).add(a);
}
colors = new int[V + 1];
for(int j = 1; j <= V; j++) {
if(!flag) break;
if(colors[j] == 0) {
bfs(j);
}
}
System.out.println(flag ? "YES" : "NO");
}
}
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<Integer>();
q.offer(start);
colors[start] = 1;
while(!q.isEmpty()) {
int cur = q.poll();
for(int next : map.get(cur)) {
// 아직 방문하지 않았다면
if(colors[next] == 0) {
q.offer(next);
// 인접한 노드는 다른 색으로 색칠
colors[next] = colors[cur] * -1;
// 1과 -1이 만나 0이 된다면 인접한 노드는 같은 색상을 가진 노드 이므로 이분 그래프 성립X
}else if(colors[cur] + colors[next] != 0) {
flag = false;
}
}
}
}
}- 이분 그래프를 처음에 잘못 이해하여서 산으로 갔다. 쉬운 개념으로 보이나 처음에는 생소한 개념이라서 잘못 이해하기 쉽상인데 이해만 한다면 간단한 그래프 탐색 문제이다. 먼저 방문하지 않은 노드를 방문 한 다음 색상을 하나 칠해준다. 그 다음 방문할 노드에는 다른 색삭을 칠해준다. 방문하지 않은 노드들을 계속 방문 하면서 인접한 노드들은 방문한 노드와는 다른 색상으로 칠해주다가 인접한 노드끼리 같은 색상 이라면 이분 그래프가 아니므로 탐색 종료,, 모두 탐색하였는데 모든 인접한 서로 다른 노드끼리 색상이 다르다면 이분 그래프 성립
8. 이모티콘(14226)
👉 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int emo;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
emo = Integer.parseInt(st.nextToken());
System.out.println(bfs());
br.close();
}
public static int bfs() {
Queue<Emoticon> q = new LinkedList<Emoticon>();
q.offer(new Emoticon(1, 0, 0));
boolean[][] visited = new boolean[10001][10001];
while(!q.isEmpty()) {
Emoticon emoticon = q.poll();
int screen = emoticon.screen;
int clip = emoticon.clip;
int time = emoticon.time;
// 종료조건
if(screen == emo) return time;
// 복사
if(!visited[screen][screen]) {
q.offer(new Emoticon(screen, screen, time + 1));
visited[screen][screen] = true;
}
// 붙혀넣기
if(!visited[screen + clip][clip]) {
q.offer(new Emoticon(screen + clip, clip, time + 1));
visited[screen + clip][clip] = true;
}
// 삭제
if(screen - 1 > 0 && !visited[screen - 1][clip]) {
q.offer(new Emoticon(screen - 1, clip, time + 1));
visited[screen - 1][clip] = true;
}
}
return 0;
}
static class Emoticon {
int screen;
int clip;
int time;
public Emoticon (int screen, int clip, int time) {
this.screen = screen;
this.clip = clip;
this.time = time;
}
}
}- 스크린, 클립보드, 시간을 객체로 하여 큐에 담아서 풀이하였고, 방문 처리 부분이 생긱이 나지 않아 블로그를 참고해가면서 풀이를 진행했다. 암만 해도 생각해도 이차원 배열로 방문 처리를 체크할 생각은 못했다,, 이런 생각은 나는 왜 안나는지ㅜ 복사, 붙혀넣기, 삭제 나누어서 수행을 해주다가 만들고자하는 이모티콘 개수를 만나면 종료