[백준 JAVA] 회귀한 프로그래머의 그래프 1 다시풀기

ABCDE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static int N, M;
    public static List<Integer>[] list;
    public static int[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 1. 입력값 받아오기
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList[N];
        visited = new int[N];
        for(int i = 0; i < N; i++){
            list[i] = new ArrayList<>();
        }
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }
        for(int i = 0; i < N; i++){
            visited[i] = 1;
            dfs(i, 1);
            visited[i] = 0;
        }

        System.out.println(0);
    }
    public static void dfs(int cur, int depth){
        if(depth == 5){
            System.out.println(1);
            System.exit(0);
        }

        for(int next : list[cur]){
            if(visited[next] == 1) continue;
            visited[next] = 1;
            dfs(next, depth + 1);
            visited[next] = 0;
        }
    }
}

 

이렇게 앞뒤로 방문체크해주는게 좀더 섹시한 코드같다.

public class Main {
        for(int i = 0; i < N; i++){
            dfs(i, 1);
        }
    }
    public static void dfs(int cur, int depth){
        if(depth == 5){
            System.out.println(1);
            System.exit(0);
        }
        visited[cur] = 1;
        for(int next : list[cur]){
            if(visited[next] == 1) continue;

            dfs(next, depth + 1);
        }
        visited[cur] = 0;
    }
}

 

DFS 와 BFS 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N, M, V;
    public static List<Integer>[] list;
    public static int[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 1. 입력값 받아오기
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        list = new ArrayList[N + 1];
        visited = new int[N + 1];
        for(int i = 1; i < N + 1; i++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            list[v1].add(v2);
            list[v2].add(v1);
        }

        for(int i = 1; i < N + 1; i++){
            list[i].sort((o1, o2) -> Integer.compare(o1, o2));
        }

        dfs(V);
        System.out.println();
        bfs();
    }

    public static void dfs(int cur){
        visited[cur] = 1;
        System.out.print(cur + " ");
        for(int next : list[cur]){
            if(visited[next] == 1) continue;
            dfs(next);
        }
    }

    public static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(V);
        visited[V] = 0;
        while(!q.isEmpty()){
            int cur = q.poll();
            System.out.print(cur + " ");
            for(int next : list[cur]){
                if(visited[next] == 0) continue;
                visited[next] = 0;
                q.offer(next);
            }
        }
    }

}

 

진짜 오랜만에 풀었는데 감회가 새롭다.

 

연결 요소의 개수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N, M, ans = 0;
    public static List<Integer>[] list;
    public static int[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 1. 입력값 받아오기
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList[N + 1];
        visited = new int[N + 1];
        for(int i = 1; i < N + 1; i++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            list[v1].add(v2);
            list[v2].add(v1);
        }
        for(int i = 1; i < N + 1; i++){
            if(visited[i] == 1) continue;
            ans++;
            dfs(i);
        }

        System.out.println(ans);
    }

    public static void dfs(int cur){
        visited[cur] = 1;
        for(int next : list[cur]){
            if(visited[next] == 1) continue;
            dfs(next);
        }
    }
}

 

이분 그래프

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int V, E;
    public static List<Integer>[] list;
    public static int[] visited;
    public static boolean ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for(int testcase = 0; testcase < T; testcase++){
            // 1. 입력값 받아오기
            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            visited = new int[V + 1];

            list = new ArrayList[V + 1];
            for(int i = 1; i < V + 1; i++){
                list[i] = new ArrayList<>();
            }

            for(int i = 0; i < E; i++){
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                list[u].add(v);
                list[v].add(u);
            }

            // 2. 그래프 탐색
            bfs();
        }
    }

    public static void bfs(){
        Queue<Integer> q = new LinkedList<>();

        for(int i = 1; i < V + 1; i++){
            if(visited[i] == 1 || visited[i] == 2) continue;
            visited[i] = 1;
            q.offer(i);

            while(!q.isEmpty()){
                int cur = q.poll();
                for(int next : list[cur]){
                    if(visited[next] == visited[cur]) {
                        System.out.println("NO");
                        return;
                    }

                    if(visited[next] == 0) {
                        q.offer(next);
                        if(visited[cur] == 1) visited[next] = 2;
                        else visited[next] = 1;
                    }
                }
            }
        }
        System.out.println("YES");
    }
}

 

이분그래프가 뭔지 몰라서 보고 푼 문제 사실 개념을 알았어도 못풀었을꺼같다.

 

if(visited[next] == visited[cur]) {
    System.out.println("NO");
    return;
}

if(visited[next] == 0) {
    q.offer(next);
    if(visited[cur] == 1) visited[next] = 2;
    else visited[next] = 1;
}

 

핵심이라 생각되는 부분은 이부분

 

처음 만난 노드라면 현재 색과 반대 색을 넣어서 방문처리 해주고

 

이후에 인접한 노드가 같은 색이라면 NO 출력

 

단지번호 붙이기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N, cnt, ans = 0;
    public static int[][] map;
    public static int[] dr = {1, 0, -1, 0};
    public static int[] dc = {0, 1, 0, -1};
    public static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 입력값 받아오기
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for(int i = 0; i < N; i++){
            String s = br.readLine();
            for(int j = 0; j < N; j++){
                map[i][j] = s.charAt(j) - '0';
            }
        }

        // 2. 그래프 탐색
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(map[i][j] == 0) continue;
                map[i][j] = 0;
                cnt = 1;
                dfs(i, j);
                ans++;
                list.add(cnt);
            }
        }
        Collections.sort(list);

        System.out.println(ans);
        for(int a : list){
            System.out.println(a);
        }
    }

    public static void dfs(int r, int c){
        for(int d = 0; d < 4; d++){
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == 0) continue;
            cnt++;
            map[nr][nc] = 0;
            dfs(nr, nc);
        }
    }
}

 

섬의 개수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int w, h, ans;
    public static int[][] map;
    public static int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0};
    public static int[] dc = {-1, 0, 1, 1, 1, 0, -1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        while(true) {
            st = new StringTokenizer(br.readLine());

            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            if (w == 0 && h == 0) break;

            map = new int[h][w];

            for (int i = 0; i < h; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            ans = 0;

            // 2. 그래프 탐색
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == 0) continue;
                    dfs(i, j);
                    ans++;
                }
            }

            System.out.println(ans);
        }
    }

    public static void dfs(int r, int c){
        map[r][c] = 0;
        for(int d = 0; d < 8; d++){
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(nr < 0 || nr >= h || nc < 0 || nc >= w || map[nr][nc] == 0) continue;
            dfs(nr, nc);
        }
    }
}

 

미로탐색

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N, M;
    public static int[][] map;
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};
    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());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }

        // 2. 그래프 탐색
        bfs();
    }
    public static void bfs(){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {0, 0, 1});
        map[0][0] = 0;
        while(!q.isEmpty()){
            int[] cur = q.poll();

            if(cur[0] == N-1 && cur[1] == M-1) {
                System.out.println(cur[2]);
                return;
            };

            for(int d = 0; d < 4; d++){
                int nr = cur[0] + dr[d];
                int nc = cur[1] + dc[d];
                if(nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc] == 0) continue;
                map[nr][nc] = 0;
                q.offer(new int[] {nr, nc, cur[2] + 1});
            }
        }
    }
}

 

토마토

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N, M, zero = 0;
    public static int[][] map, visited;
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};
    public static Queue<int[]> q;
    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 int[N][M];
        q = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1){
                    visited[i][j] = 1;
                    q.add(new int[] {i, j});
                } else if(map[i][j] == 0){
                    zero++;
                } else {
                    visited[i][j] = 1;
                }
            }
        }
        // 2. 그래프 탐색
        bfs();

    }
    public static void bfs(){
        int cnt = 0;
        while(!q.isEmpty()){
            if(zero == 0) {
                System.out.println(cnt);
                return;
            }
            cnt++;
            int size = q.size();

            for(int i = 0; i < size; i++) {
                int[] cur = q.poll();
                for(int d = 0; d < 4; d++){
                    int nr = cur[0] + dr[d];
                    int nc = cur[1] + dc[d];
                    if(nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc] == 1 || map[nr][nc] == 1) continue;
                    q.offer(new int[] {nr, nc});
                    visited[nr][nc] = 1;
                    zero--;
                }
            }
        }
        System.out.println(-1);
    }
}

 

나이트 이동

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int l, tr, tc;
    public static int[][] visited;
    public static int[] dr = {-1, -2, -2, -1, 1, 2, 2, 1};
    public static int[] dc = {-2, -1, 1, 2, 2, 1, -1, -2};
    public static Queue<int[]> q;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for(int testcase = 1; testcase <= T; testcase++){
            l = Integer.parseInt(br.readLine());
            visited = new int[l][l];

            // 1-1. 현재 위치 입력 및 방문처리
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            q = new LinkedList<>();
            q.offer(new int[] {r, c});
            visited[r][c] = 1;

            // 1-2. 가야할 위치 입력 받기
            st = new StringTokenizer(br.readLine());
            tr = Integer.parseInt(st.nextToken());
            tc = Integer.parseInt(st.nextToken());

            // 2. 그래프 탐색
            bfs();
        }

    }
    public static void bfs(){
        int cnt = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                int[] cur = q.poll();
                if(cur[0] == tr && cur[1] == tc){
                    System.out.println(cnt);
                    return;
                }
                for(int d = 0; d < 8; d++){
                    int nr = cur[0] + dr[d];
                    int nc = cur[1] + dc[d];

                    if(nr < 0 || nr >= l || nc < 0 || nc >= l || visited[nr][nc] == 1) continue;
                    visited[nr][nc] = 1;
                    q.offer(new int[] {nr, nc});
                }
            }
            cnt++;
        }
    }
}