티스토리 뷰
목차
1. 토마토(7569)
👉 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import javax.swing.plaf.synth.SynthSeparatorUI;
public class Main {
static int width, height, H, notT = 0, count = 0;
static int[][][] arr;
static int[] moveX = {-1, 1, 0, 0, 0, 0};
static int[] moveY = {0, 0, -1, 1, 0, 0};
static int[] moveH = {0, 0, 0, 0, -1, 1};
static Queue<int[]> okT = new LinkedList<int[]>();
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
width = Integer.parseInt(st.nextToken());
height = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
arr = new int[H][height][width];
for(int i = 0; i < H; i++) {
for(int j = 0; j < height; j++) {
String[] tmp = br.readLine().split(" ");
for(int k = 0; k < width; k++) {
arr[i][j][k] = Integer.parseInt(tmp[k]);
if(Integer.parseInt(tmp[k]) == 0) {
notT++;
}else if(Integer.parseInt(tmp[k]) == 1) okT.offer(new int[]{i, j, k});
}
}
}
bfs();
System.out.println(notT == 0 ? count : -1);
}
public static void bfs() {
while(notT > 0 && !okT.isEmpty()) {
int size = okT.size();
for(int i = 0; i < size; i++) {
int c = okT.peek()[0];
int b = okT.peek()[1];
int a = okT.peek()[2];
okT.poll();
for(int j = 0; j < 6; j++) {
int nC = c + moveH[j];
int nB = b + moveY[j];
int nA = a + moveX[j];
if(nA < 0 || nB < 0 || nC < 0 || nA >= width || nB >= height || nC >= H) {
continue;
}else if(arr[nC][nB][nA] != 0)
continue;
notT--;
arr[nC][nB][nA] = 1;
okT.offer(new int[] {nC, nB, nA});
}
}
count++;
}
}
}2. 적록색약(10026)
👉 소스코드
import java.util.*;
import java.io.*;
public class Main {
static int N;
static char[][] arr;
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());
arr = new char[N][N];
visited = new boolean[N][N];
for(int i = 0; i < N; i++) {
arr[i] = br.readLine().toCharArray();
}
// 일반인 대상
int totalCount = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
char c = arr[i][j];
if(!visited[i][j]) {
bfs(i, j, c);
totalCount++;
}
// 일반인 대상 탐색한 후, 적록색약자 탐색하기 위해 변경해줌
if(arr[i][j] == 'R') arr[i][j] = 'G';
}
}
visited = new boolean[N][N];
// 적록색약자 대상
int rgCount = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
char c = arr[i][j];
if(!visited[i][j]) {
bfs(i, j, c);
rgCount++;
}
}
}
System.out.println(totalCount + " " + rgCount);
}
public static void bfs(int x, int y, char color) {
Queue<int[]> q = new LinkedList<int[]>();
q.offer(new int[] {x, y});
visited[x][y] = true;
while(!q.isEmpty()) {
int curX = q.peek()[0];
int curY = q.peek()[1];
q.poll();
for(int i = 0; i < 4; i++) {
int nextX = curX + moveN[i];
int nextY = curY + moveM[i];
if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= N || visited[nextX][nextY]) continue;
if(arr[nextX][nextY] == color) {
visited[nextX][nextY] = true;
q.offer(new int[] {nextX, nextY});
}
}
}
}
}- 일반인 대상으로 먼저 탐색 시작
인접한 영역에 같은 색이 있는지 찾고 탐색이 끝나면 적록색약자를 탐색하기 위하여 'R'와 'G'를 한가지 색상으로 변경해주었다.
변경하고 난 맵을 다시한번 더 탐색
- 아래는 dfs로 풀이
public static void dfs(int x, int y, char color) {
visited[x][y] = true;
for(int i = 0; i < 4; i++) {
int nextX = x + moveN[i];
int nextY = y + moveM[i];
if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= N || visited[nextX][nextY]) continue;
if(arr[nextX][nextY] == color) {
dfs(nextX, nextY, color);
}
}
}3. 4연산(14395)
👉 소스코드
import java.util.*;
import java.io.*;
public class Main {
static int S, T;
static HashSet<Integer> set = new HashSet<Integer>();
static StringBuilder sb = new StringBuilder();
static long[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
T = Integer.parseInt(st.nextToken());
if(S == T) {
System.out.println(0);
}else if(T == 1){
System.out.println("/");
}else {
bfs(S);
}
}
public static void bfs(int start) {
Queue<Cal> q = new LinkedList<Cal>();
q.offer(new Cal(start, ""));
set.add(start);
while(!q.isEmpty()) {
Cal c = q.poll();
String operator = c.value;
if(c.num == T) {
if(!set.contains(T)) {
System.out.println("-1");
}else{
System.out.println(operator);
}
return;
}
for(int i = 0; i < 3; i++) {
long number = c.num;
if(i == 0) number *= number;
else if(i == 1) number += number;
else if(i == 2) number /= number;
if(set.contains((int)number)) continue;
if(number > T) continue;
if(i == 0) q.offer(new Cal((int)number, operator + "*"));
else if(i == 1) q.offer(new Cal((int)number, operator + "+"));
else if(i == 2) q.offer(new Cal((int)number, operator + "/"));
set.add((int) number);
}
}
System.out.println(-1);
}
static class Cal {
int num;
String value;
public Cal (int num, String value) {
this.num = num;
this.value = value;
}
}
}- 10⁹ 라는 제한이 있어서 배열로 방문처리하기에는 무리가 있어 연산한 수에 대하여 set으로 방문 처리를 했다.
이미 있으면 set에 담지 않고 연산한 수와, String에 연산자를 큐에 담아서 풀이를 진행하였다.
4. 로봇 청소기14503)
👉 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
// 14503
static int[] moveN = {-1, 0, 1, 0};
static int[] moveM = {0, 1, 0, -1};
static int cnt = 1;
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N, M, r, c, d;
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
map = new int[N][M];
for(int i = 0; i < N; i++) {
String[] s = br.readLine().split(" ");
for(int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(s[j]);
}
}
dfs(r, c, d, N, M);
System.out.println(cnt);
}
public static void dfs(int r, int c, int d, int N, int M) throws IOException {
map[r][c] = -1;
for(int i = 0; i < 4; i++) {
d = (d + 3) % 4;
int nextX = r + moveN[d];
int nextY = c + moveM[d];
if(nextX >= 0 && nextY >= 0 && nextX < N && nextY < M && map[nextX][nextY] == 0) {
cnt++;
dfs(nextX, nextY, d, N, M);
return;
}
}
int back = (d + 2) % 4;
int backX = r + moveN[back];
int backY = c + moveM[back];
if(backX >= 0 && backY >= 0 && backX < N && backY < M && map[backX][backY] != 1) {
dfs(backX, backY, d, N, M);
}
}
}- 처음부터 dfs 방식을 떠올리지 못했는데 그래프 탐색 방법에 대해서 다시 한번 짚어야 겠다는 생각을 하였다. 기존의 dfs탐색에서 방향을 가지고 청소할 곳이나 사방이 벽일 때 후진하는 로직이 주요했다. mod 연산자를 좀 더 활용하는 방법으로 로직을 설계하도록 하는 습관을 길러야겠다. 갈길이 멀다,,
5. ABCDE(13023) https://www.acmicpc.net/problem/13023
👉 소스코드
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 N, M, cnt;
static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
static boolean[] visited;
static boolean flag = false;
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());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for(int i = 0; i < N; i++) {
map.add(new ArrayList<Integer>());
}
visited = new boolean[N];
for(int i = 0; i < M; i++) {
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);
}
for(int i = 0; i < M; i++) {
if(cnt == 0) {
dfs(i, 1);
}
if(flag) break;
}
bw.write((flag ? 1 : 0) + "\n");
bw.flush();
br.close();
}
public static void dfs(int x, int y) {
if(y == 5) {
flag = true;
return;
}
visited[x] = true;
for(int i : map.get(x)) {
if(!visited[i]) {
dfs(i, y+1);
}
}
if(flag) return;
visited[x] = false;
}
}- 일반적인 dfs 문제지만 주의사항이 몇가지 있다.
- 친구 관계를 오인하는 경우가 있음 - > 인접 리스트를 생성할 때 A와 B가 친구고 B와 C가 친구이면 A와 C도 친구가 될 수 있다고 생각하여 두 인접 리스트에도 추가하는 경우인데, 주어진 입력 정보는 친구 즉, 간선 정보 이기때문에 예시를 든 것 같이 친구 관계는 중복 될 수 없음을 인지하고 풀이를 했어야 한다.
- 노드가 일직선상에 있는지 판단을 잘못하는 경우
- 그리고 모두 방문된 노드에 대한 true는 false로 변경할 것
6. 토마토(7576) https://www.acmicpc.net/problem/13023
👉 소스코드
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 M, N, count, notTo;
static int[][] map;
static boolean[][] visited;
static int[] moveN = {0, 0, -1, 1}, moveM = {-1, 1, 0, 0};
static Queue<Tomato> okTo = new LinkedList<Tomato>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = 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++) {
map[i][j] = Integer.parseInt(s[j]);
if(map[i][j] == 0) notTo++;
else if(map[i][j] == 1) okTo.offer(new Tomato(i, j));
}
}
bfs();
System.out.println(notTo == 0 ? count : -1);
}
public static void bfs() {
while(notTo > 0 && !okTo.isEmpty()) {
int size = okTo.size();
for(int i = 0; i < size; i++) {
Tomato t = okTo.poll();
int curN = t.x;
int curM = t.y;
for(int j = 0; j < 4; j++) {
int nextN = curN + moveN[j];
int nextM = curM + moveM[j];
if(nextN < 0 || nextM < 0 || nextN >= N || nextM >= M) continue;
if(map[nextN][nextM] != 0) continue;
notTo--;
okTo.offer(new Tomato(nextN, nextM));
map[nextN][nextM] = 1;
}
}
count++;
}
}
static class Tomato {
int x;
int y;
public Tomato (int x, int y) {
this.x = x;
this.y = y;
}
}
}-토마토(7569)와 동일한 문제 처음에 입력받을 때 당시 익은 토마토의 위치는 큐에다가 집어넣고 익지 않은 토마토는 개수만 세어준 후 익은 토마토의 개수만큼 반복문을 돌려주면서 상하좌우 익을 수 있는 토마토가 있는지 체크해가면서 counting 하면 되는 문제
7. 숨바꼭질 3(13549) https://www.acmicpc.net/problem/13549
👉 소스코드
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.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int subin, sister;
public static void main(String[] args) throws IOException {
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(oneZeroBfs());
br.close();
}
public static int oneZeroBfs() {
Deque<Integer> q = new ArrayDeque<Integer>();
q.offer(subin);
int[] visited = new int[100001];
Arrays.fill(visited, Integer.MAX_VALUE);
visited[subin] = 0;
while(!q.isEmpty()) {
int cur = q.poll();
if(cur == sister) return visited[sister];
if(cur * 2 <= 100000 && visited[cur * 2] > visited[cur]) {
visited[cur * 2] = visited[cur];
q.offerFirst(cur * 2);;
}
if(cur + 1 <= 100000 && visited[cur + 1] > visited[cur] + 1) {
visited[cur + 1] = visited[cur] + 1;
q.offerLast(cur + 1);
}
if(cur - 1 >= 0 && visited[cur - 1] > visited[cur] + 1) {
visited[cur - 1] = visited[cur] + 1;
q.offerLast(cur - 1);
}
}
return 0;
}
}- 순간이동을 하는 경우 (X*2) 때문에 가선의 가중치가 달라진다. 그러므로 일반적인 bfs가 아닌 0-1 bfs로 풀이 진행했다. 현재 수빈이가 있는 자리 + 1 (시간을 소비하여 행위를 하는 경우)이 현재 수빈이가 있는 자리 + 가중치 보다 크다면 해당 행위를 진행하고, 배열에 표시되어 있는 자리에 값을 갱신하여 주면 된다. (아래는 다익스트라 코드로 풀이한 방법)
public static int dijkstra() {
PriorityQueue<Loc> q = new PriorityQueue<Loc>();
q.offer(new Loc(subin, 0));
boolean[] visited = new boolean[maxNum + 1];
visited[subin] = true;
while(!q.isEmpty()) {
Loc l = q.poll();
visited[l.start] = true;
if(l.start == sister) return l.count;
if(l.start * 2 <= maxNum && !visited[l.start * 2]) {
q.offer(new Loc(l.start * 2, l.count));
}
if(l.start + 1 <= maxNum && !visited[l.start + 1]) {
q.offer(new Loc(l.start + 1, l.count + 1));
}
if(l.start - 1 >= 0 && !visited[l.start - 1]) {
q.offer(new Loc(l.start - 1, l.count + 1));
}
}
return 0;
}
static class Loc implements Comparable<Loc>{
int start, count;
public Loc(int start, int count) {
this.start = start;
this.count = count;
}
@Override
public int compareTo(Loc l) {
return this.count - l.count;
}
}
}