그래프 탐색 유형 오답노트

정리

그래프 탐색

바이러스 - 실버3

https://www.acmicpc.net/problem/2606

 

문제 유형:

• 노드 형태의 그래프 형태
• 시작점에 연결된 노드의 개수를 세는 문제
• 노드 관점의 그래프 자료구조를 사용했을떄 dfs/bfs 아무거나 상관x
  • 그냥 연결된 모든 노드를 탐방을 하고 연결된 노드 개수를 세는 문제 -> 스택 or 큐에 넣을때마다 count 증가

 

단지번호붙이기 - 실버1

https://www.acmicpc.net/problem/2667

 

문제 유형: 

• 2차원 배열 형태의 그래프 형태
• 연결된 모든 노드의 개수를 세는 문제
  
  • 즉, 모든 노드를 시작점으로 다 탐색을 해야함

 

해결책:

• graph[1][1] ~ graph[n][n]까지 모든 노드를 시작 지점으로 하고 탐색을 진행
  • 단, 이미 방문한 노드이거나 탐색 불가 지역(예: 벽)이면 탐색x

 

• 노드 관점에서는 이웃 노드를 간선 정보를 확인해야 했지만, 2차원 배열 형태는 상하좌우가 기본적으로 연결이 되어있는 형태
• 따라서, 방향 벡터로 이웃된 4개의 노드를 다음 탐색에 넣을지 말지 판단하면 되는 것 

 

2차원 배열 형태 그래프 탐색에서 필요한 것

2차원 배열 형태의 그래프와 방문 확인 배열	bfs	2차원 배열 위치

 

핵심은 2차원 배열 형태는 어차피 상하좌우가 다 연결이 되어있기에 노드의 값(2차원 배열 값)만 입력받아 방향 벡터로 처리하는 방향으로 가자

 

package org.woojin.graphSearch;

import java.io.*;
import java.util.*;
public class 단지번호붙이기 {

    static int n;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.valueOf(br.readLine());

        graph = new int[n+1][n+1];
        visited = new boolean[n+1][n+1];
        //입력
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                graph[i+1][j+1] = line.charAt(j) - '0';
            }
        }
        //입력

        ArrayList<Integer> result = new ArrayList<>();
        for(int i=1; i<=n; i++){
            for (int j=1; j<=n; j++){
                if(graph[i][j]== 0 || visited[i][j]){
                    continue;
                }
                result.add(bfs(i,j));
            }
        }

        Collections.sort(result);

        StringBuilder sb = new StringBuilder();
        sb.append(result.size()).append("\n");
        for(int r : result){
            sb.append(r).append("\n");
        }
        System.out.println(sb);
    }

    public static int bfs(int x, int y) {
        Stack<Node> s = new Stack<>();
        s.push(new Node(x,y));
        visited[x][y] = true;

        int count = 1;
        while(!s.isEmpty()){
            Node now = s.pop();

            //방향 벡터 버전
            for(int i=0; i<4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if(nx >= 1 && nx <= n  && ny >= 1 && ny <= n){
                    if(graph[nx][ny] != 0 && !(visited[nx][ny])){
                        s.push(new Node(nx, ny));
                        visited[nx][ny] = true;
                        count++;
                    }
                }
            }
        }
        return count;
    }

    static class Node{
        int x;
        int y;

        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }



}

 

 

 

봄버맨 - 실버1

 

문제 유형

• 2차원 배열 형태의 그래프 형태
• 연결된 노드에 작업을 하는 문제 ( 폭탄 폭발 처리 )

 

해결 방법

• 매초마다 폭탄이 폭발 처리만 bfs/dfs를 사용해서 하는 문제
• 매초마다 폭탄 심고, 폭탄 카운트 다운 하는건 따로 구현해야하는 문제였음 ( 코드가 덕분에 길어짐 )

 

package org.woojin.graphSearch;
import java.io.*;
import java.util.*;

public class 붐버맨 {

    static int r;
    static int c;
    static int n;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.valueOf(st.nextToken());
        c = Integer.valueOf(st.nextToken());
        n = Integer.valueOf(st.nextToken());

        graph = new int[r+1][c+1];
        visited = new boolean[r+1][c+1];

        String str;
        for(int i=1; i<=r; i++){
            str = br.readLine();
            for(int j=0; j<c; j++){
                if(str.charAt(j) == 'O'){
                    graph[i][j+1] = 3;
                }
            }
        }

        if(n<=1){
            printGraph();
            return;
        }

        for(int i=2; i<=n; i++){
            countBom();

            if(i % 2 == 0){
                makeBom();
            }
            resetVisited();
            checkBfs();
        }

        printGraph();
    }

    // 한번의 bfs를 수행 후 방문 배열 초기화
    public static void resetVisited(){
        for(int i=1; i<=r; i++){
            Arrays.fill(visited[i], false);

        }
    }

    // 폭탄 설치 함수
    public static void makeBom(){
        for(int i=1; i<=r; i++) {
            for (int j = 1; j <= c; j++) {
                if(graph[i][j] == 0){
                    graph[i][j] = 4;
                }
            }
        }
    }

    // 폭탄 시간 감소 ( 1이 되면 터짐 )
    public static void countBom(){
        for(int i=1; i<=r; i++) {
            for (int j = 1; j <= c; j++) {
                if(graph[i][j] > 1){
                    graph[i][j] -= 1;
                }
            }
        }
    }

    // 2차원 배열 그래프 각 지점마다다 bfs 시작
    public static void checkBfs(){
        for(int i=1; i<=r; i++) {
            for (int j = 1; j <= c; j++) {
                //단, 방문x + 폭탄 시간이 1 남은 것만 bfs시작
                if((!visited[i][j]) && graph[i][j] == 1 ){
                    bfs(i,j);
                }
            }
        }
    }

    public static void bfs(int x, int y){
        Stack<Node> s = new Stack<>();

        s.push(new Node(x,y));
        visited[x][y] = true;

        while(!s.isEmpty()){
            Node now = s.pop();
            graph[x][y] = 0;

            for(int i=0; i<4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if(nx >= 1 && nx <= r && ny >=1 && ny <= c){
                    //이웃노드 폭탄 처리 하는데
                    if(!visited[nx][ny]){
                        //이웃 노드도 폭탄 시간이 1 남았으면 동시 폭발을 위해 추가 탐색
                        if(graph[nx][ny] == 1){
                            s.push(new Node(nx, ny));
                        }
                        graph[nx][ny] = 0;
                        visited[nx][ny] = true;
                    }
                }
            }
        }

    }

    public static void printGraph(){
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=r; i++){
            for(int j=1; j<=c; j++){
                if(graph[i][j] != 0){
                    sb.append('O');
                } else {
                    sb.append('.');
                }
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }

    static class Node{
        int x;
        int y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }


}