[삼성SDS] 24년 하반기 대학생 알고리즘 특강(Day1) : 알고리즘 기초(DFS, BFS)

*DFS, BFS는 그래프 알고리즘에서 기초가 되는 탐색 방식으로 반드시 숙지가 필요하다.

 

DFS

• 깊이 우선 탐색(Depth First Search)
• 그래프 탐색 방법의 한가지
• 한 경로로 탐색하다 특정 상황에서 최대한 깊숙하게 들어가서 확인 후 다시 돌아가 다른 경로로 탐색하는 방식
• 일반적으로 재귀함수를 사용하여 풀이한다.(stack을 사용하는 문제는 거의 드물다)
• 백트레킹, 단절선 찾기, 단절점 찾기, 위상정렬, 사이클 찾기 등에 사용된다.

 

풀이 팁

• 현재 방문하고 있는 노드에만 관여한다.
• 필요한 정보(부모가 누구인지, 얼마나 걸렸는지)는 코드를 작성하다 추가하도록 한다.
• 추가하는 방식은 1) 파라미터로 넘기기 2) static 전역 변수 선언하기 방식이 있다.

 

풀이 순서 (들여쓰기 주의)

1. 체크인
   • 단순 방문 여부만 체크하는 1차원 배열일 때는 boolean[] visited로 선언하고 그 외의 거리합을 저장할 때에는 int[][] dp로 선언한다.
2. 목적지인가
3. 연결된 곳을 순회
   • 연결되었지만, 갈 수 없는 곳이 존재할 수 있다.
4. _갈 수 있는가
   • 방문 여부로 갈 수 있는지 체크한다.
5. __간다
   • dfs() 호출
6. 체크아웃 (*체크인과 같은 인덴트에 위치해야한다)

 

 

예제 문제

백준 1759번 : 암호 만들기

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

 

public class Main {

	static int L, C;
	static String[] alphabet;
	static boolean[] visited;
	static StringBuilder sb = new StringBuilder();
	static int depth = 0;
	static String vowel = "aeiou";
	static int vowelCnt = 0;
	
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src/SDS/P1759/input.txt"));
		Scanner sc = new Scanner(System.in);
		
		L = Integer.parseInt(sc.next());
		C = Integer.parseInt(sc.next());
		
		alphabet = new String[C];
		visited = new boolean[C];
		
		for (int i = 0; i < C; i++) {
			alphabet[i] = sc.next();
		}
		
		Arrays.sort(alphabet);
		
		for (int i = 0; i < C; i++) {
			dfs(i);
		}
		
		System.out.println(sb);
		sc.close();
	}
}

	private static void dfs(int idx) {
		//1. 체크인
		visited[idx] = true;
		depth++;
		if (vowel.contains(alphabet[idx])) vowelCnt++;
		
		//2. 목적지인가?
		if (depth >= L) {
			//답 출력
			if (L - vowelCnt >= 2 && vowelCnt >= 1) {
				for (int i = 0; i < visited.length; i++) {
					if (visited[i]) {
						sb.append(alphabet[i]);
					}
				}
				sb.append("\n");
			}
		} else {
			//3. 연결된 곳들 순회
			for (int i = idx + 1; i < C; i++) {
				//4. 갈 수 있는가 
				if (!visited[i]) {
					//5. 간다
					dfs(i);
				}
			}
		}
		
		//6. 체크아웃
		visited[idx] = false;
		depth--;
		if (vowel.contains(alphabet[idx])) vowelCnt--;
	}

 

길이를 체크하는 depth는 전역변수로 설정하여 체크인과 함께 수정되도록 하였다.

조건 중 모음은 최소 1개 이상, 자음은 최소 2개 이상 존재해야하므로 알파벳 4개가 조합이 되었을 때 조건 체크 후 값에 저장한다.

 

 

---

BFS

• 너비 우선 탐색(Breadth First Search)
• 그래프 탐색 방법의 한가지
• 시작 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방식
• 일반적으로 Queue 자료구조를 이용하여 구현한다.
• 최단경로 찾기, 위상정렬 등에 사용된다.

 

*DFS로 풀이가 안되고, BFS만 해결 가능한 문제 특징

• 동시성을 가진다.
• 한 칸 움직일 때, 값이 변하며 다음 방문에 영향을 끼친다.
• 대표적인 문제로는 썩은 토마토 문제가 있다.

 

풀이 순서 (들여쓰기 주의)

1. 큐에서 poll
2. 목적지인가
3. 연결된 곳을 순회
4. _갈 수 있는가
5. __체크인
   • 큐에 add하여 다음 방문할 예정으로 저장한다.
6. 체크아웃 (BFS 에서 거의 필요없는 단계)

 

예제 문제

백준 3055번 : 탈출

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

 

	private static void bfs() {
		
		while (!que.isEmpty()) {
			//1. 큐에서 poll
			Point point = que.poll();
			int x = point.x;
			int y = point.y;
			char type = point.type;
			
			//2. 목적지(= D) 인가
			if (type == 'S' && map[y][x] == 'D') {
				//최단 경로 계산
				result = visited[y][x];
				break;
			}
			
			//3. 연결된 곳을 순회
			for (int i = 0; i < 4; i++) {
				int nextY = y + MY[i];
				int nextX = x + MX[i];
				//4. 갈 수 있는가
				boolean flag = isGo(nextY, nextX, type);
				
				//5. 체크인
				if (flag) {
					que.add(new Point(nextY, nextX, type));
					if (type == 'S') {
						visited[nextY][nextX] = visited[y][x] + 1;
					} else if (type == '*') {
						map[nextY][nextX] = '*';
					}
				}
			}
		}
		
	}