[2025 1학기 알고리즘 스터디] 윤성욱 #4주차

미로 탐색

import java.io.*;
import java.util.*;
import java.awt.Point;
public class Main{
    static int dx[] = {0,0,-1,1};
    static int dy[] = {-1,1,0,0};
    static int arr[][],N,M;
    static boolean visit[][];
    static int count = 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());
        arr = new int[N][M];
        visit = new boolean[N][M];
        
        for(int i =0; i<N; i++){
            String s = br.readLine();
            for(int j =0; j<M; j++){
                arr[i][j] = s.charAt(j)- '0';
            }
        }
        
        bfs(0,0);
        System.out.println(arr[N-1][M-1]);
    }
    
    static void bfs(int x, int y){
        Queue<Point> que = new LinkedList<>();
        que.add(new Point(x,y));
        visit[x][y]=true;
        
        while(!que.isEmpty()){
            Point p = que.poll();
            for(int i =0; i<4; i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(0<=nx && nx<N && 0<=ny && ny<M && !visit[nx][ny] && arr[nx][ny]>0){
                    que.add(new Point(nx, ny));
                    visit[nx][ny] = true;
                    arr[nx][ny] = arr[p.x][p.y] + 1;
                }
           }
        }
    }
}

연결 요소의 개수

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();

        boolean[][] adj = new boolean[N + 1][N + 1];
        for (int i = 0; i < M; i++) {
            int n1 = sc.nextInt(), n2 = sc.nextInt();

            adj[n1][n2] = adj[n2][n1] = true;
        }

        boolean[] visit = new boolean[N + 1];
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            if (!visit[i]) {
                dfs(i, N, adj, visit);
                ans++;
            }
        }

        System.out.println(ans);

    }

    static void dfs(int n, int N, boolean[][] adj, boolean[] visit) {
        visit[n] = true;

        for (int i = 1; i <= N; i++) {
            if (!visit[i] && adj[i][n])
                dfs(i, N, adj, visit);
        }
    }
}

 

BFS와 DFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
	static int[][] arr;
	static boolean[] visit;
	static int n;
	static int m;
	static int start;
    public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		start = scan.nextInt();
		arr = new int[1001][1001];
		visit = new boolean[1001];
		
		for(int i = 0; i < m; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			arr[x][y] = arr[y][x] = 1;
		}
		dfs(start);
		visit = new boolean[1001];
		System.out.println();
		bfs();
    }
    public static void dfs(int i) {
    	visit[i] = true;
    	System.out.print(i + " ");
    	for(int j = 1; j <= n; j++) {
    		if(arr[i][j] == 1 && visit[j] == false) {
    			dfs(j);
    		}
    	}
    }
    public static void bfs() {
    	Queue<Integer>queue = new LinkedList<Integer>();
    	queue.offer(start);
    	visit[start] = true;
    	System.out.print(start + " ");
    	while(!queue.isEmpty()) {
    		int temp = queue.poll();
    		for(int j = 1; j <= n; j++) {
    			if(arr[temp][j] == 1 && visit[j] == false) {
    				queue.offer(j);
    				visit[j] = true;
    				System.out.print(j + " ");
    			}
    		}
    	}
    }
}