codejcd 기술 블로그

문제

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

분석/설계

맵을 탐색하는 DFS/BFS 유형의 문제이고 보통 2차원 배열 형태의 맵을 주고 조건을 달리하면서

탐색하는 형태 유형으로 많이 출제되는 것 같습니다.

기존 상하좌우만 탐색하는 케이스와 달리 대각선까지 탐색하기 때문에 이를 탐색하기 위한 값들을 잘 정의해줘야합니다.

구현 코드

package backjoon;

import java.util.Scanner;

public class Main {
	static int T; // 테스트 케이스 횟수
	static int M; // 배추 심어진 가로 길이
	static int N; // 배추 심어진 세로 개수
	static int K; // 배추가 심어진 위치의 개수
	static int[][] map; // 배추밭
	static boolean[][] visited; //
	static int cnt; // 필요한 지렁이 
	static int[] dx = {0, -1, 0, 1}; // 상하좌우 탐색을 위한 값들
	static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt(); // 테스트 케이스 개수
		
		for(int i=0; i<T; i++) {	// 입력 초기화
			cnt = 0;
			M = scanner.nextInt();
			N = scanner.nextInt();
			K = scanner.nextInt();
			
			map = new int[M][N];
			visited = new boolean[M][N];
			
			for(int j=0; j<K; j++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();	
				map[x][y] = 1;
			}
			
			for(int v=0; v<M; v++) {
				for(int w=0; w<N; w++) {
					if (map[v][w] == 1 && !visited[v][w]) {
						dfs(v, w);
						cnt++;
					}
				}
			}
			System.out.println(cnt);

		}
		scanner.close();
	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int mx = x + dx[i];
			int my = y + dy[i];
			
			if (mx >= 0 && my >= 0 && mx < M && my < N) { // 0 보다 크고 맵 크기보다는 작아야한다.
				if(!visited[mx][my] && map[mx][my] == 1) { // 방문 여부와 배추가 심어진 곳을 체크
					dfs(mx, my);
				}
			}
		}
	}
}

정리

입력받는 변수가 여러 개이므로 놓치지 않고 어떤 변수에 저장할지 정리하여

DFS 구현에 필요한 변수와 함께 정의합니다.

그 외에  탐색을 위한 값들도 정의해주고 이를 DFS 구현 시 적용하는 게 핵심입니다.

구현이 끝나면  간단하지만 어떻게 탐색하고 카운트할지 고민하고 구현에 들어가야 합니다.

참고

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

문제

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

분석/설계

그래프를 탐색하는 DFS/BFS 유형의 문제입니다.

구현 시 주의할 점은 방문을 체크하는 배열을 크기를 +1 해줘야 합니다.

그렇지 않을 경우 조건에서 N이 1부터 시작하기 때문에 마지막 수를 체크할 때  

Array 크기를 초과하여 Exception이 발생하게 됩니다.

구현 코드

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

public class Main {
	static int N; // 정점 개수
	static int M; // 간선 개수
	static boolean[] visited; // 방문한 곳
	static ArrayList<ArrayList<Integer>> map = new ArrayList<>(); // 그래프
	static int cnt; // 연결 요소의 개수 
	
	public static void dfs(int v) {
		visited[v] = true;
		
		for (int i=0; i<map.get(v).size(); i++) {
			int w = map.get(v).get(i);
			if (!visited[w]) dfs(w);
		}
	}
	
	public static void bfs(int v) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(v);

		visited[v] = true;
		
		while(!queue.isEmpty()) {
			int x= queue.poll();
		
			for (int i=0; i<map.get(v).size(); i++) {
				int w = map.get(x).get(i);
				if(!visited[w]) {
					queue.offer(w);
					visited[w] = true;
				}	
			}
			
		}
		
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		N = scanner.nextInt();
		M = scanner.nextInt();
		
		for(int i=0; i<=N; i++) {
			map.add(new ArrayList<>());
		}
		
		visited = new boolean[N+1];
		
		for (int i=0; i<M; i++) {
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			map.get(v1).add(v2);
			map.get(v2).add(v1);
		}
		
		for(int i=1; i<=N; i++) {
			if(!visited[i]) {
				dfs(i);
				cnt++;
			}
		}	
		System.out.println(cnt);
		scanner.close();
	}
}

정리

간단하지만 조건을 정확하게 확인해야 실수를 줄일 수 있습니다.

참고

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

문제

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

분석/설계

맵을 탐색하는 DFS/BFS 유형의 문제이고 보통 2차원 배열 형태의 맵을 주고 조건을 달리하면서

탐색하는 형태 유형으로 많이 출제되는 것 같습니다.

구현 코드

package backjoon;

import java.util.Scanner;

public class Main {
	static int T; // 테스트 케이스 횟수
	static int M; // 배추 심어진 가로 길이
	static int N; // 배추 심어진 세로 개수
	static int K; // 배추가 심어진 위치의 개수
	static int[][] map; // 배추밭
	static boolean[][] visited; //
	static int cnt; // 필요한 지렁이 
	static int[] dx = {0, -1, 0, 1}; // 상하좌우 탐색을 위한 값들
	static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt(); // 테스트 케이스 개수
		
		for(int i=0; i<T; i++) {	// 입력 초기화
			cnt = 0;
			M = scanner.nextInt();
			N = scanner.nextInt();
			K = scanner.nextInt();
			
			map = new int[M][N];
			visited = new boolean[M][N];
			
			for(int j=0; j<K; j++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();	
				map[x][y] = 1;
			}
			
			for(int v=0; v<M; v++) {
				for(int w=0; w<N; w++) {
					if (map[v][w] == 1 && !visited[v][w]) {
						dfs(v, w);
						cnt++;
					}
				}
			}
			System.out.println(cnt);

		}
		scanner.close();
	}
	
	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int mx = x + dx[i];
			int my = y + dy[i];
			
			if (mx >= 0 && my >= 0 && mx < M && my < N) { // 0 보다 크고 맵 크기보다는 작아야한다.
				if(!visited[mx][my] && map[mx][my] == 1) { // 방문 여부와 배추가 심어진 곳을 체크
					dfs(mx, my);
				}
			}
		}
	}
}

정리

입력받는 변수가 여러 개이므로 놓치지 않고 어떤 변수에 저장할지 정리하여

DFS 구현에 필요한 변수와 함께 정의합니다.

그 외에 상하좌우 탐색을 위한 값들도 정의해주고 이를 DFS 구현 시 적용하는 게 핵심입니다.

구현이 끝나면  간단하지만 어떻게 상하좌우를 탐색하고 카운트할지 고민하고 구현에 들어가야 합니다.

참고

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

문제

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

분석/설계

전형적인 그래프를 탐색하는 DFS/BFS 유형의 문제이고

그래프 상 노드(컴퓨터)가 100대 이하이므로 완전 탐색으로 접근 가능한 문제로 파악했고

DFS로 구현했습니다.

구현 코드

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

public class Main {
	
	static boolean[] visted;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	
	public static void dfs(int V) {
		visted[V] = true;

		for(int i=0; i<graph.get(V).size(); i++) {
			int W = graph.get(V).get(i);
			if(!visted[W]) dfs(W);	
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt(); // 컴퓨터 수
		int M = scanner.nextInt(); // 연결된 컴퓨터 쌍의 수
		
		for(int i=0; i<=N; i++) { // 인접 배열 리스트 초기화
			graph.add(new ArrayList<Integer>());
		}
		
		visted = new boolean[N+1]; // 방문 여부 판단할 배열
		
		scanner.nextLine();
		for(int i=0; i<M; i++) { // 인접 배열 리스트 값 세팅 
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			graph.get(v1).add(v2); 
			graph.get(v2).add(v1);
		}
		
		dfs(1);
		
		int cnt = 0;
		for(int i=0; i<visted.length; i++) {
			if(visted[i]) cnt++;
		}
		System.out.println(cnt-1);
		scanner.close();
	}
}

정리

문제를 읽어보면 1번 컴퓨터부터 시작한다는 조건이 있고 

1번 컴퓨터를 통해 바이러스에 걸리는 컴퓨터 수를 구해야하므로

1번 컴퓨터까지 카운트된 숫자는 제외해줍니다.

참고

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

문제

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

분석/설계

DFS와 BFS로 완전 탐색하여 접근하는 방향으로 가닥을 잡고

인접한 상하좌우를 탐색하는 것이므로 BFS가 구현이 쉬울 것 같아 선택했다.

다른 문제들과 달리 한칸씩 띄워서 입력 받지 않기때문에 이런 부분이 조금 달랐던 것 같고

결국 입력 값을 받아 초기화하고 BFS로 어떻게 기준을 잡고 탐색하는지가 중요했던 문제입니다.

구현 코드

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

class Dot{ // X,Y 좌표를 저장하는 클래스
	int x;
	int y;
	
	public Dot(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}				
}

public class Main {
	static ArrayList<Integer> count = new ArrayList<>();
	 // 상, 하, 좌, 우를 탐색하기 위한 배열
	static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
	
	public static void bfs(int arr[][], boolean visited[][], Dot dot) {
		Queue<Dot> q = new LinkedList<Dot>();
		q.offer(dot);
		visited[dot.getX()][dot.getY()] = true;
		int cnt = 0; // 주변에 존재하는 집의 수를 저장
		
		while(!q.isEmpty()) {
			Dot temp = q.poll();
			int x = temp.getX();
			int y = temp.getY();
			cnt++;
			
			for(int i=0; i<4; i++) { // 상하좌우 탐색
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				// 맵의 범위를 벗어나는 좌표는 무시
				if(nx>=arr.length || nx<0 || ny>=arr[nx].length || ny < 0) continue;
				
				// 이미 방문한 경우도 무시
				if(visited[nx][ny]) continue;
				
				if(arr[nx][ny] == 1) {
					visited[nx][ny] = true;
					q.offer(new Dot(nx, ny));
				}
			}
		}
		count.add(cnt);
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt(); // 맵의 크기 N
		int arr[][] = new int[N][N]; // N x N map
		boolean visited[][] = new boolean[N][N]; // N x N 크기의 방문여부 배열
		
		scanner.nextLine();
		for(int i=0; i<arr.length; i++) { // 맵 입력 받은 값으로 초기화
			String[] temp = scanner.nextLine().split("");
			for(int j=0; j<arr[i].length; j++) {
				arr[i][j] = Integer.parseInt(temp[j]);
			}
		}
		Dot dot;
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr[i].length; j++) {
				if(arr[i][j] == 1 && visited[i][j] == false) { // 맵을 탐색하면서 아파트이면서 방문하지 않은경우
					dot = new Dot(i, j);
					bfs(arr, visited, dot);
				}
			}
		}
			
		System.out.println(count.size());
		Collections.sort(count);
		for(int i=0; i<count.size(); i++) {
			System.out.println(count.get(i));
		}
		
		
		scanner.close();
	}
}

정리

좌표에 대해서 어떻게 코드로 구현할지

BFS를 구현할 때 큐에 넣고 큐에서 꺼내는 기준을 무엇으로 할지가 핵심이고

답을 구하기 위해서 어떤 값이 필요할지 처음에 잘 정의한다면 그렇게 어려운 문제는 아닙니다.

FS나 DFS를 어떻게 응용할지 많이 문제를 접해봐야할 것 같습니다.

참고

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

이번 문제는 백준 알고리즘 사이트에 문제입니다.

DFS와 BFS 관련 문제로 기본/핵심 적인 문제입니다.

문제

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

분석/설계

제목 부터과 DFS/BFS 이여서 당연히 DFS/BFS로 접근하였습니다.

기본적인 DFS/BFS 구현과 유사하지만 두 정점 사이에 여러개의 간선과 양방향 이라는 점에서 주의해야합니다.

처음에 양방향을 생각하지 않고 풀이 했을대, 예제 1번은 답이 나왔지만 2,3 번은 모두 오답이 었습니다. 

구현 코드

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

public class DFSBFS {

	static boolean[] visted;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	
	public static void dfs(int V) {
		visted[V] = true;
		System.out.print(V + " ");
		
		for(int i=0; i<graph.get(V).size(); i++) {
			int W = graph.get(V).get(i);
			if(!visted[W]) dfs(W);	
		}
	}
	
	public static void bfs(int V) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(V);
		
		visted[V] = true;
		
		while(!queue.isEmpty()) {
			int x = queue.poll();
			System.out.print(x + " ");
			for(int i=0; i<graph.get(x).size(); i++) {
				int W = graph.get(x).get(i);
				if(!visted[W]) {
					queue.offer(W);
					visted[W] = true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = scanner.nextInt(); // 정점의 개수
		int M = scanner.nextInt(); // 간선 열결하는 두 정점의5 번호
		int V = scanner.nextInt(); // 시작할 정점 번호
		
		for(int i=0; i<=N; i++) { // 인접 배열 리스트 초기화
			graph.add(new ArrayList<Integer>());
		}
		
		visted = new boolean[N+1]; // 방문 여부 판단할 배열
		
		scanner.nextLine();
		for(int i=0; i<M; i++) { // 인접 배열 리스트 값 세팅 
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			graph.get(v1).add(v2); 
			graph.get(v2).add(v1);
		}
		
		for(int i=1;i<=N;i++) { // 이동 간선의 이동 경우가 다수 존재할 경우 작은 정점부터 이동해야하므로 오름차순 정렬
			Collections.sort(graph.get(i));
		}
		
		dfs(V);
		visted = new boolean[N+1]; // dfs 수행 후 방문 여부 판단할 배열 초기화
		System.out.println();
		bfs(V);
		scanner.close();
	}
}

정리

DFS 재귀 함수로 BFS는 Queue를 이용해서 구현했다.

기본적인 그래프에 대한 DFS/BFS 를 구현하는 문제였고 사소한 구현 사항을 놓치지 않으면

쉽게 풀수 있는 문제입니다. 

참고

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