지금의 기록이 미래의 자산이 된다.

Today's records become tomorrow's assets.

[백준] 4963. 섬의 개수

2023-12-05

devFancy

Algorithm
문제 링크

성능 요약
- 메모리: 16012 KB, 시간: 176 ms
구분
- 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색
Answer Code

```java // 섬의 개수([백준] 4963.) - 23.12.04 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer;

public class Number_of_Islands { static final int MAX = 50 + 10; static boolean[][] map; static boolean[][] visited; static int M, N; static int[] dirY = {-1, -1, 0, 1, 1, 1, 0, -1}; // 상하좌우, 대각선 포함 - 8개 방향 static int[] dirX = {0, 1, 1, 1, 0, -1, -1, -1};

public static void dfs(int y, int x) { visited[y][x] = true; for(int i = 0; i < 8; i++) { int newY = y + dirY[i]; int newX = x + dirX[i]; if(map[newY][newX] && visited[newY][newX] == false) { dfs(newY, newX); } }

}

public static void main(String[] args) throws IOException { // 0. 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Read All
[백준] 1388. 바닥장식

2023-12-05

devFancy

Algorithm
문제 링크

성능 요약
- 메모리: 14196 KB, 시간: 128 ms
구분
- 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현
Answer Code1(23.12.05)

```java // 바닥장식([백준] 4963.) import java.util.; import java.io.;

class FloorDecoration { static final int MAX = 50 + 10; static char[][] map; static boolean[][] visited;

public static void dfs(int y, int x) { visited[y][x] = true;
```
if(map[y][x] == '-' && map[y][x+1] == '-') {
  dfs(y, x+1);
}
if(map[y][x] == '|' && map[y+1][x] == '|') {
  dfs(y+1, x);
}
```
} public static void main(String[] args) throws IOException { // 0. 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
```
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

map = new char[MAX][MAX];
visited = new boolean[MAX][MAX];
```
Read All

[solved.ac] Class3++ 1012. 유기농 배추

2023-12-04

devfancy

Algorithm

성능 요약
구분
Answer Code1(2023.02.09) - BFS
Answer Code2(2023.02.09) - DFS

문제 링크

성능 요약

메모리: 16044 KB, 시간: 164 ms - Answer Code2(2023.02.09) - BFS
메모리: 16236 KB, 시간: 160 ms - Answer Code1(2023.02.09) - DFS
메모리: 15792 KB, 시간: 164 ms - Answer Code3(2023.12.04) - DFS

구분

그래프 이론(graphs), 그래프 탐색(graph_traversal), 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs)

Answer Code1(2023.02.09) - 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[][] ground;      //2차원 배열로 배추밭을 표현한다
    static boolean[][] check;   //2차원 배열로 배추가 있는 곳을 체크한다
    static int weight;          //배추밭의 가로
    static int height;          //배추밭의 세로

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            weight = Integer.parseInt(st.nextToken());
            height = Integer.parseInt(st.nextToken());
            ground = new int[weight][height];
            check = new boolean[weight][height];

            int K = Integer.parseInt(st.nextToken());
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                ground[x][y] = 1;   //배추 좌표 입력
            }
            //===========================================================
            //여기까지는 입력된 내용 저장하는 내용이다.

            int count=0;    //테스트 케이스마다 지렁이의 개수를 세야한다
            
            //bfs의 시작좌표를 셋팅해서 다른 곳에 모여있는 배추들도 파악할 수 있게한다
            //가로 세로 좌표들을 하나씩 입력해주고
            for (int j = 0; j < weight; j++) {
                for (int k = 0; k < height; k++) {
                    
                    //좌표에 배추가 있는지 확인, 내가 체크안한 곳인지 확인한다
                     if(ground[j][k] == 1 && !check[j][k]){
                         //배추가 있고 체크안된 좌표에서부터 bfs로 연결된 곳을 파악한다
                         bfs(j, k);
                         
                         //지렁이의 개수는 인접한 곳마다 1개씩이다.
                         //인접한 곳을 모두 파악했으면 지렁이를 한마리 놓는다.
                         count++;
                     }
                }
            }

            System.out.println(count);
        }

    }

    private static void bfs(int startX, int startY) {
        Queue<int[]> queue = new LinkedList<>();
        //bfs에서 queue의 역할은 다음 탐색할 좌표를 미리 저장해 놓는 것이다.
        //bfs 1번 실행될때마다 인접한 곳을 모두 탐색하고 종료되니 bfs안에 queue를 선언했다.
        
        queue.offer(new int[] {startX, startY});
        //x, y좌표 저장
        
        check[startX][startY] = true;
        //시작좌표엔 배추가 있으니 미리 true로 처리해준다.
        
        int[] X = {0, 0, -1, +1};
        int[] Y = {-1, +1, 0, 0};
        //배추가 상하좌우에 인접하면 이동할 수 있다.
        //현재좌표에서 상하좌우 움직이는 좌표를 지정한다.

        //queue가 비어있으면 더이상 인접한 배추가 없다는 뜻이다.
        while(!queue.isEmpty()){
            int[] poll = queue.poll();
            //저장된 queue를 꺼낸다
            
            //상하좌우 4가지 방법이니 for문 4번 반복
            for (int i = 0; i < 4; i++) {
                int x = poll[0] + X[i];
                int y = poll[1] + Y[i];
                //상하좌우 좌표 조정

                //좌표가 배추밭을 벗어나게되면 다음 좌표를 체크해야한다
                if(x < 0 || x >= weight || y < 0 || y >= height){
                    continue;
                }

                //상하좌우 움직인 좌표에 배추가 있고, 체크하지 않은 좌표이면
                if(ground[x][y] == 1 & !check[x][y]){
                    queue.offer(new int[] {x, y});
                    //좌표를 저장한다.
                    check[x][y] = true;
                    //체크한다
                }

            }
        }

    }

}

Answer Code2(2023.02.09) - DFS

```java 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[][] ground;      //2차원 배열로 배추밭을 표현한다
static boolean[][] check;   //2차원 배열로 배추가 있는 곳을 체크한다
static int weight;          //배추밭의 가로
static int height;          //배추밭의 세로

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    StringTokenizer st;
    for (int i = 0; i < T; i++) {
        st = new StringTokenizer(br.readLine(), " ");
        weight = Integer.parseInt(st.nextToken());
        height = Integer.parseInt(st.nextToken());
        ground = new int[weight][height];
        check = new boolean[weight][height];

        int K = Integer.parseInt(st.nextToken());
        for (int j = 0; j < K; j++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            ground[x][y] = 1;   //배추 좌표 입력
        }
        //===========================================================
        //여기까지는 입력된 내용 저장하는 내용이다.

        int count=0;    //테스트 케이스마다 지렁이의 개수를 세야한다

        //bfs의 시작좌표를 셋팅해서 다른 곳에 모여있는 배추들도 파악할 수 있게한다
        //가로 세로 좌표들을 하나씩 입력해주고
        for (int j = 0; j < weight; j++) {
            for (int k = 0; k < height; k++) {

                //좌표에 배추가 있는지 확인, 내가 체크안한 곳인지 확인한다
                 if(ground[j][k] == 1 && !check[j][k]){
                     //배추가 있고 체크안된 좌표에서부터 dfs로 연결된 곳을 파악한다
                     dfs(j, k);

                     //지렁이의 개수는 인접한 곳마다 1개씩이다.
                     //인접한 곳을 모두 파악했으면 지렁이를 한마리 놓는다.
                     count++;
                 }
            }
        }

        System.out.println(count);
    }

}

private static void dfs(int startX, int startY) {
    check[startX][startY] = true;
    //시작좌표엔 배추가 있으니 미리 true로 처리해준다.

    int[] X = {0, 0, -1, +1};
    int[] Y = {-1, +1, 0, 0};
    //배추가 상하좌우에 인접하면 이동할 수 있다.
    //현재좌표에서 상하좌우 움직이는 좌표를 지정한다.

    //상하좌우 4가지 방법이니 for문 4번 반복
    for (int i = 0; i < 4; i++) {
        int x = startX + X[i];
        int y = startY + Y[i];
        //상하좌우 좌표 조정

        //좌표가 배추밭을 벗어나게되면 다음 좌표를 체크해야한다
        if(x < 0 || x >= weight || y < 0 || y >= height){
            continue;
        }

        //상하좌우 움직인 좌표에 배추가 있고, 체크하지 않은 좌표이면
        if(ground[x][y] == 1 & !check[x][y]){
            dfs(x, y);	//해당 좌표로 dfs 실행
        }

    }

Read All

[백준] 13565. 침투

2023-12-04

devFancy

Algorithm

성능 요약
구분
Answer Code1(23.12.04)
- 문제풀이
Answer Code2(24.01.16)
정리
Review

문제 링크

성능 요약

메모리: 53320 KB, 시간: 1356 ms
메모리: 54268 KB, 시간: 696 ms

구분

그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색

Answer Code1(23.12.04)

// 침투 (백준 13565)
import java.util.*;
import java.io.*;

class Penetrate {
  static final int MAX = 1000 + 10;
  static boolean[][] map;
  static boolean[][] visited;
  static int M, N;
  static int dirX[] = {-1, 1, 0, 0};
  static int dirY[] = {0, 0, -1, 1};
  static boolean answer;

  public static void dfs(int y, int x) {
    if(y == N) {
      answer = true;
      return;
    }

    visited[y][x] = true;
    for(int i = 0; i < 4; i++) {
      int newX = x + dirX[i];
      int newY = y + dirY[i];
      if(map[newY][newX] && visited[newY][newX] == false)
        dfs(newY, newX);
    }
  }

  public static void main(String[] args) throws IOException {
    // 0. 입력 및 초기화
    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());

    // 1. map에 정보 반영하기
    map = new boolean[MAX][MAX];
    visited = new boolean[MAX][MAX];

    for(int i = 1; i <= N; i++) {
      String str = br.readLine();
      for(int j = 1; j <= M; j++)
        map[i][j] = (str.charAt(j - 1) == '0' ? true : false);

    }

    // 2. dfs 수행
    for(int j = 1; j <= M; j++) {
      if(map[1][j]) {
        dfs(1, j);
      }
    }

    // 3. 출력
    if(answer) bw.write("YES");
    else bw.write("NO");

    bw.close();
    br.close();
  }
}

문제풀이

이 문제에서 DFS를 떠올릴 수 있는 키워드는 다음과 같다.
- 상하좌우로 인접한 흰색 격자들
- 안쪽까지 침두될 수 있는지 아닌지를 판단
문제에서는 전류가 흐르는 것을 ‘0’으로 해주고, 흐르지 않는 것을 ‘1’로 나와있는데, 이는 문제를 풀때 헷갈릴 수 있다.

그래서 전류가 흐르는 것을 ‘1’로 하고, 흐르지 않는 것을 ‘0’으로 해주기 위해 바꿔주는 로직을 구성한다.

이 문제에서 핵심은 내가 방문하고자 하는 곳을 1로 하는 것이 훨씬 더 유리하다.
이 문제에서는 첫 번째 줄에서 시작해서 마지막에 도달할 수 있는지 판단하는 것이므로 dfs(1, j)라고 해준 것이다.

[1]. map에 정보 반영하기

이중 반복문을 통해 해당 위치에 해당하는 값이 0일 경우, ‘1’로 바꿔준다.

[2]. dfs 수행

처음 시작 위치가 1부터 시작하기 때문에 dfs(1, j)과 같이 표현한 것이고,
M번 만큼 반복하면서 값이 true일 경우에 한해서만 dfs를 수행하기 때문에 for문 안에 조건문인 if(map[1][j])을 추가해준 것이다.
dfs를 수행할 때, 상하좌우로 확인하므로 반복문 for(int i = 0; i < 4; i++)과 방향에 대한 dirX, dirY를 선언해줬다.

그리고 상하좌우를 확인할 때, map에 해당하는 값이 true(1)이고, 방문한 적이 없을 경우에만 dfs를 다시 호출하도록 했다.
마지막으로 dfs 메서드 시작할 때, if(y == N)을 한 이유는 안쪽까지 도달했는지 확인하기 위해서다.

만약 안쪽까지 도달했다면, 즉 N번 줄에 도달했다면 침투를 했다는 의미이므로 answer 값을 true로 바꿔주고 return 해주면 된다.

[3]. 출력

출력할 때는 answer가 true이면 YES를 출력하고, 그게 아니라면 NO를 출력해주면 된다.

visited 없이 map으로만 구현하기

아래는 visited 없이 map으로도 구현한 코드이다.

import java.util.*;
import java.io.*;

class Penetrate {
    static final int MAX = 1000 + 10;
    static boolean[][] map;
    static int M, N;
    static int dirX[] = {-1, 1, 0, 0};
    static int dirY[] = {0, 0, -1, 1};
    static boolean answer;

    public static void dfs(int y, int x) {
        if(y == N) {
            answer = true;
            return;
        }

        map[y][x] = false;
        for(int i = 0; i < 4; i++) {
            int newX = x + dirX[i];
            int newY = y + dirY[i];
            if(map[newY][newX])
                dfs(newY, newX);
        }
    }

    public static void main(String[] args) throws IOException {
        // 0. 입력 및 초기화
        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());

        map = new boolean[MAX][MAX];

        // 1. map에 정보 반영하기
        for(int i = 1; i <= N; i++) {
            String str = br.readLine();
            for(int j = 1; j <= M; j++) {
                map[i][j] = (str.charAt(j - 1) == '0' ? true : false);
            }
        }

        // 2. dfs 수행
        for(int j = 1; j <= M; j++) {
            if(map[1][j])
                dfs(1, j);
        }

        // 3. 출력
        if(answer) bw.write("YES");
        else bw.write("NO");

        bw.close();
        br.close();
    }
}

Answer Code2(24.01.16)

package DFS;
// 24.01.16 침투 복습
import java.util.*;
import java.io.*;

class Penetrate_2 {
    static final int MAX = 1000 + 10;
    static boolean[][] map;
    static int N, M;
    static boolean answer;

    static int[] dirX = {-1, 1, 0, 0};
    static int[] dirY = {0, 0, -1, 1};

    public static void dfs(int x, int y) {
        if(x == N) {
            answer = true;
            return;
        }
        map[x][y] = false;
        for(int i = 0; i < 4; i++) {
            int newX = x + dirX[i];
            int newY = y + dirY[i];
            if(map[newX][newY]) {
                dfs(newX, newY);
            }
        }

    }
    public static void main(String[] args) throws IOException {
        
        // 0. 입력 및 초기화
        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());

        // 1. map에 정보반영
        map = new boolean[MAX][MAX];

        for(int i = 1; i <= N; i++) {
            String str = br.readLine();
            for(int j = 1; j <= M; j++) {
                map[i][j] = (str.charAt(j - 1) == '0' ? true : false);
            }
        }
        
        // 2. bfs 호출
        for(int j = 1; j <= M; j++) {
            if(map[1][j]) {
                dfs(1, j);
            }
        }

        // 3. 출력
        if(answer) bw.write("YES");
        else bw.write("NO");
        
        bw.close();
        br.close();
    }
}

정리

문제를 풀기 시작하기 전에, 아래 5가지를 생각해보면서 접근해보자.

상하좌우로 인접한 흰색 격자들로 전달 -> DFS/BFS
서로 연결되었다는 정보를 어떻게 하나의 자료구조로 통합할까? -> 2차원 배열
이미 방문한 지점을 다시 방문하지 않으려면 어떤 자료구조를 사용해야 할까?
visited 배열을 생략할 수는 없을까?
어느 지점에서 dfs를 시작할까?

Review

visited 없이 map으로만 할 경우 처리 시간이 1892(ms) -> 1356(ms) 줄었다는 걸 확인할 수 있다.
그래도 이해를 위해 우선 visited 변수를 사용해서 풀어보고, 완전히 dfs를 이해했다면 이후에는 visited 없이도 바로 생각할 수 있도록 하자.

Read All

[백준] 11725. 트리의 부모찾기

2023-12-01

devFancy

Algorithm

성능 요약
구분
Answer Code
문제풀이
Review

문제 링크

성능 요약

71236 KB, 시간: 596 ms

구분

그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색

Answer Code

import java.util.*;
import java.io.*;

class TreeParentSearch {
    static final int MAX = 100000 + 10;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int N;
    static int[] answer;

    public static void dfs(int idx) {
        visited[idx] = true;
        for(int i = 0; i < graph[idx].size(); i++) {
            int next = graph[idx].get(i);
            if(visited[next] == false) {
                answer[next] = idx;
                dfs(next);
            }
        }
    }

    public static void main(String[] args) throws IOException{
        // 0. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        
        graph = new ArrayList[MAX];
        for(int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        visited = new boolean[MAX];
        answer = new int[MAX];

        // 1. 연결 정보 채우기
        int x, y;
        for(int i = 0; i < N-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            graph[x].add(y);
            graph[y].add(x);
        }

        // 2. dfs(재귀 함수) 호출하기
        dfs(1);

        // 3. 출력
        for(int i = 2; i <= N; i++) {
            bw.write(String.valueOf(answer[i]));
            bw.newLine();
        }
        bw.close();
        br.close();
    }
}

문제풀이

‘각 노드의 부모를 구하라’ => 다른 말로 **연결되어 있는 상태에서 각 노드의 상위 노드가 누구인지 찾는 문제였다.
그리고 트리의 루트를 1이라고 문제에서 주어졌기 때문에, 최상단 노드는 1부터 시작한다는 의미이다. => dfs(1);

class TreeParentSearch {
    public static void dfs(int idx) {
        visited[idx] = true;
        for (int i = 0; i < graph[idx].size(); i++) {
            int next = graph[idx].get(i);
            if (visited[next] == false) {
                answer[next] = idx;
                dfs(next);
            }
        }
    }
}

우선 해당 노드를 방문했기 때문에, visited[idx] = true;를 해준다.
그런 다음, graph[idx].size(); 만큼 반복문을 돌리는 것인데,

해석하자면, ArrayList<Integer>[]형인 graph에서 해당 index에 있는 size만큼 반복문을 돌리는 것이다.

예를 들어, 첫번째 예시에서 연결된 두 정점을 통해 1이 연결된 값이 4와 6이라면, 1에 해당하는 size, 즉 graph[1].size()는 2개를 의미한다.
그리고 next = graph[idx].get(i);을 해석하자면,

문제에서 연결된 두 정점을 바탕으로 ArrayList를 그려보면, graph[1].get(0); = 6이라는 값이 next 변수에 넣어주게 된다.

그런 다음, 아직 방문하지 않았다면, dfs(재귀 함수)를 호출한다.

이때, dfs(재귀 함수)를 호출하기 이전에, 부모 노드인 값(idx)을 answer라는 변수에 담아준다.

예를 들어, 1번째 인덱스에서 6이라는 녀석에 dfs를 호출하는데, 6의 부모 노드의 값이 1이므로 answer[6] = 1과 같이 answer라는 변수에 담아준다.

그리고 dfs(6)을 호출한다.

Review

해당 문제를 아래와 같이, 그림을 그리면서 푸니까 확실히 이해가 되면서 정답을 맞출 수 있었다.

매번 이러한 유형의 문제를 접할때 마다 그래프라는 자료구조를 어떻게 잡아야 할지,

그리고 재방문은 어떻게 방지할지,

마지막으로 정답은 어떤 자료구조에 담아야 잘 출력할지 고민하는 연습을 계속하자.
트리/각 노드의 부모를 찾아라 => DFS/BFS

문제에서 주어진 N이라는 값이 크면 ArrayList를 이용하자.

Read All

11/59

지금의 기록이 미래의 자산이 된다.

[백준] 4963. 섬의 개수

성능 요약

구분

Answer Code

[백준] 1388. 바닥장식

성능 요약

구분

Answer Code1(23.12.05)

[solved.ac] Class3++ 1012. 유기농 배추

성능 요약

구분

Answer Code1(2023.02.09) - BFS

Answer Code2(2023.02.09) - DFS

[백준] 13565. 침투

성능 요약

구분

Answer Code1(23.12.04)

문제풀이

Answer Code2(24.01.16)

정리

Review

[백준] 11725. 트리의 부모찾기

성능 요약

구분

Answer Code

문제풀이

Review