문제는 다음과 같습니다.

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

　
import java.util.Scanner;

public class Test14502 {
	static int N, M;
	static int totalCNT;
	static int[] dx = {0, -1, 0, 1};
	static int[] dy = {-1, 0, 1, 0};
	static int[][] adMatrix, visit;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		adMatrix = new int[N][M];
		visit = new int[N][M];
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				adMatrix[i][j] = sc.nextInt();
			}
		}
		//알고리즘 풀이
		for(int i=0; i<N*M; i++) {
			int row = i/M;
			int col = i%M;
			if(adMatrix[row][col]==0) {
				adMatrix[row][col]=1;
				DFS(i, 1);
				adMatrix[row][col]=0;
			}
		}
		System.out.println(totalCNT);
	}
	//벽 3개 세우기
	static void DFS(int v, int cnt) {
		int row = v/M;
		int col = v%M;
		if(cnt==3) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					visit[i][j]=adMatrix[i][j];
				}
			}
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(visit[i][j]==2) {
						spreadVirus(i, j);
					}
				}
			}
			safetyArea();
		}else {
			for(int i=v+1; i<N*M; i++) {
				int row2 = i/M;
				int col2 = i%M;
				if(adMatrix[row2][col2]==0) {
					adMatrix[row2][col2]=1;
					DFS(i, cnt+1);
				}
			}
		}
		adMatrix[row][col]=0;
	}
	//바이러스 확산 메소드
	static void spreadVirus(int row, int col) {
		for(int i=0; i<4; i++) {
			int nextRow = dx[i]+row;
			int nextCol = dy[i]+col;
			if(nextRow>=0 && nextRow<N && nextCol>=0 && nextCol<M) {
				if(visit[nextRow][nextCol]==0) {
					visit[nextRow][nextCol]=2;
					spreadVirus(nextRow, nextCol);
				}
			}
		}
	}
	//안정 영역 크기 구하기
	static void safetyArea() {
		int cnt=0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(visit[i][j]==0) {
					cnt++;
				}
			}
		}
		if(totalCNT<cnt) {
			totalCNT = cnt;
		}
	}
}

　

결과입니다.

문제는 다음과 같습니다.

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

　
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Test{
	static int N;
	static int[][] adMatrix;
	static int[][] visit;
	static int dx[] = {0, -1, 0, 1};
	static int dy[] = {-1, 0, 1, 0};
	static ArrayList<Integer> list = new ArrayList<Integer>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		adMatrix = new int[N+1][N+1];
		visit = new int[N+1][N+1];
		String[] s = new String[N+1];
		for(int i=1; i<=N; i++) {
			s[i] = sc.next();
			for(int j=1; j<=N; j++) {
				adMatrix[i][j] = s[i].charAt(j-1)-'0';
			}
		}
		
		int totalCNT=0;
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(adMatrix[i][j]==1 && visit[i][j]==0) {
					totalCNT++;
					int cnt = DFS(i,j, totalCNT, 0);
					list.add(cnt);
				}
			}
		}
		Collections.sort(list); //오름차순 정렬함수
		System.out.println(totalCNT);
		for(int x : list) {
			System.out.println(x);
		}
	}
	static int DFS(int row, int col, int totalCNT, int cnt) {
		cnt++;
		visit[row][col] = 1; //1 true, 0 false
		for(int i=0; i<4; i++) {
			int nextRow = row + dx[i];
			int nextCol = col + dy[i];
			if(nextRow>0 && nextRow<=N && nextCol>0 && nextCol<=N) {
				if(adMatrix[nextRow][nextCol]==1 && visit[nextRow][nextCol]==0) {
					cnt = DFS(nextRow, nextCol, totalCNT, cnt);
				}
			}
		}
		return cnt;
	}
	
	
}
　

결과입니다.

문제는 다음과 같습니다.

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

　
import java.util.Scanner;

public class Test11403 {
	static int N;
	static int[][] adMatrix;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		adMatrix = new int[N+1][N+1];
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				adMatrix[i][j] = sc.nextInt();
			}
		}
		//알고리즘 풀이
		for(int i=1; i<=N; i++) {
			int[] visit = new int[N+1];
			DFS(i, visit, false);
			for(int j=1; j<=N; j++) {
				System.out.print(visit[j]+" ");
			}System.out.println();
		}
	}
	static void DFS(int x, int[] visit, Boolean isFirst) {
		if(isFirst) { 
			visit[x] = 1;
		}
		for(int i=1; i<=N; i++) {
			if(adMatrix[x][i]==1 && visit[i]==0) {
				DFS(i, visit, true);				
			}
			
		}
	}
}
　

　
import java.util.Scanner;

public class Test11403{
	static int N;
	static int[][] adMatrix;
	static void DFS(int x, int[] visit, boolean isFirst) {
		if(!isFirst) { //isFirst가 false일 경우
			visit[x]=1;
		}
		for(int i=1; i<=N; i++) {
			if(adMatrix[x][i]==1 && visit[i]==0) {
				DFS(i, visit, false);
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		adMatrix = new int[N+1][N+1];
		//행렬 입력받기
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				adMatrix[i][j] = sc.nextInt();
			}
		}
		//알고리즘 풀이
		for(int i=1; i<=N; i++) {
			int[] visit = new int[N+1];
			DFS(i, visit, true);
			for(int j=1; j<=N; j++) {
				System.out.print(visit[j]+" ");
			}System.out.println();
		}
		
	}
	
}
　

　
import java.util.Scanner;

public class Test11403{
	static int N;
	static int[][] adMatrix;
	static int[][] result;
	
	static void DFS(int x, int[] visit, boolean isFirst) {
		if(!isFirst) { //isFirst가 false일 경우
			visit[x]=1;
		}
		for(int i=1; i<=N; i++) {
			if(adMatrix[x][i]==1 && visit[i]==0) {
				DFS(i, visit, false);
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		adMatrix = new int[N+1][N+1];
		result = new int[N+1][N+1];
		//행렬 입력받기
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				adMatrix[i][j] = sc.nextInt();
			}
		}
		//알고리즘 풀이
		for(int i=1; i<=N; i++) {
			int[] visit = new int[N+1];
			DFS(i, visit, true);
			result[i] = visit;
		}
		//출력하기
		for(int i=1; i<result.length; i++) {
			for(int j=1; j<result.length; j++) {
				System.out.print(result[i][j]+" ");
			}
			if(i != result.length-1) {
				System.out.println();
			}
		}
	}
	
}
　

결과입니다.

문제는 다음과 같습니다.

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

　
import java.util.Scanner;

public class Test1915{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		String[] num = new String[1001];
		int dp[][] = new int[1001][1001];
		int map[][] = new int[1001][1001];
		for(int i=1; i<=n; i++) {
			num[i] = sc.next();
			for(int j=1; j<=m; j++) {
				map[i][j] = num[i].charAt(j-1)-'0';
			}
		}
		int answer=0;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				if(map[i][j] != 0){
					int imsi = Math.min(dp[i-1][j], dp[i-1][j-1]);
					dp[i][j] = Math.min(dp[i][j-1], imsi) + 1;
					answer = Math.max(answer, dp[i][j]);
				}
			}
		}
		System.out.println(answer*answer);
	}
	
}

결과입니다.

1. 깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

장점과 단점[편집]

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
• 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

2. 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

장점과 단점[편집]

장점

• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

문제는 다음과 같습니다.

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

　
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Test1260{
	static int N,M,V;
	static int visit[], graph[][];

  static void DFS(int x) {
		visit[x]=1;
		System.out.print(x+" ");
		for(int i=1; i<=N; i++) {
			if(graph[x][i]==1 && visit[i]==0) {
				DFS(i);
			}
		}
	}
	static void BFS() {
		Queue<Integer> q = new LinkedList<Integer>();
		visit[V] = 1;
		q.add(V);
		while(!q.isEmpty()) {
			int x = q.peek(); //Queue에서 제거하며 읽기
			q.poll(); //Queue에서 제거하지 않고 읽기
			System.out.print(x+" ");
			for(int i=1; i<=N; i++) {
				if(graph[x][i]==1 && visit[i]==0) {
					visit[i]=1;
					q.add(i);
				}
			}
		}
	}

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		V = sc.nextInt();
		
		graph = new int[N+1][N+1];
		for(int i=1; i<=M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			graph[x][y]=graph[y][x]=1;
		}

		visit = new int[N+1];
		DFS(V);
		System.out.println();
		visit = new int[N+1];
		BFS();
		
	}
	
}
　

결과는 다음과 같습니다.