백준 문제풀이 (실버 1)
2023. 1. 30. 11:27ㆍ백준 문제풀이/실버1
1. 단지번호붙이기(2667)
👉 소스코드
public class Main {
static int N, count, num;
static int[][] arr;
static boolean[][] visited;
static int[] moveX = {0, 0, -1, 1};
static int[] moveY = {-1, 1, 0, 0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
ArrayList<Integer> list = new ArrayList<Integer>();
N = Integer.parseInt(st.nextToken());
arr = new int[N][N];
visited = new boolean[N][N];
for(int i = 0; i < N; i++) {
String s = br.readLine();
for(int j = 0; j < N; j++) {
arr[i][j] = Character.getNumericValue(s.charAt(j));
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(!visited[i][j] && arr[i][j] == 1) {
count = 0;
num++;
bfs(i, j);
list.add(count);
}
}
}
Collections.sort(list);
bw.append(num + "\n");
for(int i : list) {
bw.append(i + "\n");
}
bw.flush();
bw.close();
}-bfs, dfs 두 가지 방법으로 풀이를 진행했다. 입력하는 대로 받은 뒤 탐색하는 자리를 단지별로 수를 넣어준다. 인접한 자리를 모두 탐색한 뒤 0이면 다음 자리를 찾아서 탐색하는 방법으로 풀이 진행. (아래 bfs, dfs 소스 코드 참조)
-bfs
public static void bfs(int x, int y) {
Queue<int[]> q = new LinkedList<int[]>();
q.add(new int[]{x, y});
arr[x][y] = num;
visited[x][y] = true;
while(!q.isEmpty()) {
int curX = q.peek()[0];
int curY = q.peek()[1];
q.poll();
count++;
for(int i = 0; i < 4; i ++) {
int nextX = curX + moveX[i];
int nextY = curY + moveY[i];
if(nextX >= 0 && nextY >= 0 && nextX < N && nextY < N) {
if(!visited[nextX][nextY] && arr[nextX][nextY] == 1) {
arr[nextX][nextY] = num;
visited[nextX][nextY] = true;
q.add(new int[]{nextX, nextY});
}
}
}
}
}-dfs
public static void dfs(int x, int y) {
visited[x][y] = true;
arr[x][y] = num;
count++;
for(int i = 0;i < 4; i++) {
int nextX = moveX[i] + x;
int nextY = moveY[i] + y;
if(nextX >= 0 && nextY >= 0 && nextX < N && nextY < N) {
if(!visited[nextX][nextY] && arr[nextX][nextY] == 1) {
arr[nextX][nextY] = num;
dfs(nextX, nextY);
}
}
}
}2. 스타트링크(5014)
👉 소스코드
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 F, cur, goal, U, D;
static int[] visited;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
F = Integer.parseInt(st.nextToken());
cur = Integer.parseInt(st.nextToken());
goal = Integer.parseInt(st.nextToken());
U = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
visited = new int[F + 1];
int res = bfs(cur);
if(res == -1) {
System.out.println("use the stairs");
} else{
System.out.println(res);
}
}
public static int bfs(int start) {
Queue<Integer> floor = new LinkedList<Integer>();
visited[start] = 1;
floor.offer(start);
while(!floor.isEmpty()) {
int next = floor.poll();
// 목표층에 도달한 경우
if(next == goal) {
return visited[next] - 1;
}
// up버튼을 누르는경우
if(next + U <= F && visited[next + U] == 0) {
visited[next + U] = visited[next] + 1;
floor.offer(next + U);
}
// down 버튼을 누르는 경우
if(next - D > 0 && visited[next - D] == 0) {
visited[next - D] = visited[next] + 1;
floor.offer(next - D);
}
}
return -1;
}
}- 출발 층 기준으로 주어진 버튼으로 방문이 가능한 모든 층에 누름 횟수를 남기는 로직으로 풀이했다
3. 안전 영역(2468)
👉 소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[] moveX = {0, 0, -1, 1};
static int[] moveY = {-1, 1, 0, 0};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> list = new ArrayList<Integer>();
int N = Integer.parseInt(br.readLine());
int[][] stage = new int[N][N];
boolean[][] visited = new boolean[N][N];
int count = 0, ans = 0;
for(int i = 0; i < N; i++) {
String[] s = br.readLine().split(" ");
for(int j = 0; j < N; j++) {
stage[i][j] = Integer.parseInt(s[j]);
if(!list.contains(stage[i][j])) list.add(stage[i][j]);
}
}
list.add(0);
Collections.sort(list);
for(int i : list) {
// 비를 뿌려보면서 회차별로 안전한 지대 list에 추가
count = 0;
visited = new boolean[N][N];
for(int j = 0; j < N; j++) {
for(int k = 0; k < N; k++) {
if(stage[j][k] <= i) {
visited[j][k] = true;
}
}
}
for(int j = 0; j < N; j++) {
for(int k = 0; k < N; k++) {
if(!visited[j][k]) count = bfs(stage, visited, j, k, count, N);
}
}
ans = Math.max(ans, count);
}
System.out.println(ans);
}
public static int bfs(int[][]arr, boolean[][] check, int x, int y, int count, int N) {
Queue<int[]> q = new LinkedList<int[]>();
q.add(new int[] {x, y});
check[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 + moveX[i];
int nextY = curY + moveY[i];
if(nextX >= 0 && nextY >= 0 && nextX < N && nextY < N && !check[nextX][nextY]) {
check[nextX][nextY] = true;
q.add(new int[] {nextX, nextY});
}
}
}
count++;
return count;
}
}- list에 비의 양을 담아두고 리스트를 순회하면서 비가 왔을 때 잠기는 지역을 방문처리하고 탐색하면서 인접한 부분 중 잠기지 않은 그룹의 수 카운팅을 해서 풀이를 진행하였다. stage에 실제로 비를 내려주면서 했다가 삽질을 많이 했다.. 되도록이면 데이터는 만지지 않고 하도록 로직을 짜버릇 해야겠다!! 아래는 dfs 풀이 방식이다
public static int dfs(int[][]arr, boolean[][] check, int x, int y, int count, int N) {
check[x][y] = true;
count++;
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 < N && !check[nextX][nextY]) {
dfs(arr, check, nextX, nextY, count, N);
}
}
return count;
}4. 점프 게임(15558)
👉 소스코드
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 N, K;
static int[][] map;
static boolean[][] visited;
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());
K = Integer.parseInt(st.nextToken());
map = new int[2][N];
visited = new boolean[2][N];
for(int i = 0; i < 2; i++) {
String[] s = br.readLine().split("");
for(int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(s[j]);
}
}
System.out.println(bfs());
}
public static int bfs() {
Queue<Stage> q = new LinkedList<Stage>();
q.offer(new Stage(0, 0));
visited[0][0] = true;
int time = -1;
while(!q.isEmpty()) {
int length = q.size();
time++;
for(int i = 0; i < length; i++) {
Stage stage = q.poll();
int left = stage.left;
int right = stage.right;
int[][] direction = {{left, right + 1}, {left, right - 1}, {(left + 1) % 2, right + K}};
for(int j = 0; j < 3; j++) {
int nextL = direction[j][0];
int nextR = direction[j][1];
if(nextR > N-1) return 1;
if(nextR < 0 || visited[nextL][nextR] || map[nextL][nextR] == 0) continue;
if(nextR == time) continue;
visited[nextL][nextR] = true;
q.offer(new Stage(nextL, nextR));
}
}
visited[0][time] = true;
visited[1][time] = true;
}
return 0;
}
static class Stage {
int left;
int right;
public Stage (int left, int right) {
this.left = left;
this.right = right;
}
}
}- 아래그림과 같이 적어보면서 구현할려고 스텝별로 적어보았지만 블로그 보면서 겨우 이해한 문제,, 어디가 이해가 안됐나면 행동양식 3가지를 정해주는 코드가 이해가 되지 않았다. 왼쪽 줄, 오른쪽 줄 두 가지만 존재하기 때문에 0과 1로 표현이 가능하여 2차원 배열 direction에 이동할 부분에 대한 값을 미리 계산해 놓을 수 있었다.
5. 나이트의 이동(7562) https://www.acmicpc.net/problem/7562
👉 소스코드
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 T, startX, startY, finishX, finishY, size;
static int[][] map;
static int[][] visited;
static int[] moveY = {-2, -2, 2, 2, -1, -1, 1, 1},
moveX = {-1, 1, -1, 1, -2, 2, -2, 2};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++) {
size = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
map = new int[size][size];
visited = new int[size][size];
startY = Integer.parseInt(st.nextToken());
startX = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
finishY = Integer.parseInt(st.nextToken());
finishX = Integer.parseInt(st.nextToken());
sb.append(bfs()).append("\n");
}
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
public static int bfs() {
Queue<Location> q = new LinkedList<Location>();
q.offer(new Location(startY, startX));
boolean[][] check = new boolean[size][size];
check[startY][startX] = true;
while(!q.isEmpty()) {
Location l = q.poll();
int curY = l.y;
int curX = l.x;
// 종료 조건
if(curY == finishY && curX == finishX) return visited[curY][curX];
for(int i = 0; i < 8; i++) {
int nextY = curY + moveY[i];
int nextX = curX + moveX[i];
// 체스판을 벗어날 경우
if(nextY < 0 || nextX < 0 || nextY >= size || nextX >= size) continue;
if(!check[nextY][nextX]) {
visited[nextY][nextX] = visited[curY][curX] + 1;
check[nextY][nextX] = true;
q.offer(new Location(nextY, nextX));
}
}
}
return 0;
}
static class Location {
int y;
int x;
public Location (int y, int x) {
this.y = y;
this.x = x;
}
}
}- 일반적인 bfs 탐색의 경우 상하좌우 4가지 방향으로 움직이며 체크하는 경우인데, 나이트 같은 경우는 한 자리에서 움직일 수 있는 경우의 수는 8가지 이다. 이 움직임 8가지를 배열로 놓고 탐색하면 간단하게 풀이가 가능한 문제
6. 쿼드트리(1922)
👉 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] map;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
map = new int[N][N];
for(int i = 0; i < N; i++) {
String[] tmp = br.readLine().split("");
for(int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(tmp[j]);
}
}
QuadTree(0, 0, N);
System.out.println(sb.toString());
br.close();
}
static void QuadTree(int x, int y, int size) {
if(check(x, y, size)) {
if(map[x][y] == 0) sb.append("0");
else sb.append("1");
return;
} else sb.append("(");
int newSize = size / 2;
QuadTree(x, y, newSize);
QuadTree(x, y + newSize, newSize);
QuadTree(x + newSize, y, newSize);
QuadTree(x + newSize, y + newSize, newSize);
sb.append(")");
}
static boolean check(int x, int y, int size) {
int checkColor = map[x][y];
for(int i = x; i < x + size; i++) {
for(int j = y; j < y + size; j++) {
if(map[i][j] != checkColor) return false;
}
}
return true;
}
}
- 분할 정복의 기초적인 문제로써 N 값이 들어오면 0,0부터 N-1, N-1까지 확인하면서 이웃한 모든 값이 0 혹은 1인지 확인하여 모두 동일하다면 해당 값으로 압축을 진행한다.
(압축을 진행한다는 의미는 시작 값의 값 x, y의 값인 0 혹은 1로 합칠 수 있다는 의미이다)
만약 압축을 할 수 없는 경우라면 4분할하여 동일한 과정을 진행하고 만약 동일하게 압축할 수 없는 상황이라면 위 과정을 반복한다.