[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.*;

public class Main {
	
	static int[][] graph = new int[1001][1001];
	static int V;
	static int E;
	static boolean[] visited = new boolean[1001];
	
	public static void dfs(int index) {
		if(visited[index] == true)
			return;
		else {
			visited[index] = true;
			for(int i = 1; i <= V; i++) {
				if(graph[index][i] == 1) {
					dfs(i);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 
		
		V = sc.nextInt();
		E = sc.nextInt();
		
		int a,b;
		for(int i = 0; i < E; i++) {
			a = sc.nextInt();
			b = sc.nextInt();
			
			// 간선 연결
			graph[a][b] = graph[b][a] = 1;
		}
		
		int result = 0 ;
		
		// dfs 탐색
		for(int i = 1; i <= V; i++) {
			if(visited[i] == false) { // 방문한 적 없는 노드라면 dfs.
				dfs(i);
				result++;
			}
		}
		
		System.out.println(result);
		
		sc.close();
		return;
	}
}

 

BFS와 DFS

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

public class Main {
	static int Edge_arr[][];
	static boolean Visited_arr[];
	static int N;
	static int M;
	static int V;
    static int count;
	static Queue<Integer> que = new LinkedList<>();

	public static void BFS(int start) {
		que.offer(start);	
		Visited_arr[start] = true;
		System.out.print(start + " ");

		while( !que.isEmpty() ) {
			start = que.poll();

			for(int i=1; i<=N; i++) {

				if(Edge_arr[start][i] == 1 && Visited_arr[i] == false) {
					que.offer(i);
					Visited_arr[i] = true;
					System.out.print(i + " ");
				}
			}
		}	
	}

	public static void DFS(int start) {
		Visited_arr[start] = true;
		System.out.print(start + " ");

        if(count == N) {
			return;
		}
		count ++;

		for(int i=1; i<=N; i++) {
			if(Edge_arr[start][i] == 1 && Visited_arr[i] == false) {
				DFS(i);
			}
		}
	}

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

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		V = Integer.parseInt(st.nextToken());

		Edge_arr = new int[1001][1001];
		Visited_arr = new boolean[1001];

		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			Edge_arr[x][y] = Edge_arr[y][x] = 1;
		}

		DFS(V);
		System.out.println();

		Visited_arr = new boolean[1001];
		BFS(V);
	
	} 
}