개발자 교육을 듣고 있는 당신을 위해[2] - BFS/DFS(1)
참고한다는 자료는 점점 늘어간다, 뭘 하기로 마음먹으면 계속 관련된 게 알고리즘에 뜨게 되어 있으니까 ..
(올바른 표현은 아닙니다)
알고리즘 ? 어 코테?
말 나온 김에 그럼 코테 풀면 되는건가? 하면서 프로그래머스 0, 1단계 문제만 마구마구 풀어내신 여러분
걱정마세요 저도 그렇습니다 하지만 그러지 말라고 하네요!
오늘의 참고자료 : https://www.youtube.com/watch?v=iBE8trz9uHI
저는 떨어진 적 없습니다
지원횟수 : 0
*
영상 9분 쯤부터 보시면 코테 관련한 얘기가 나오고 유익하지만 요약하면 자료구조, 알고리즘에 대한 학습 없이 양치기를 해버리면 의미가 없다는것 (대부분 취준생의 시간은 넘치지 않죠)
*
https://school.programmers.co.kr/learn/courses/30/lessons/43162
LEV.3 가장 정답률 높은 문제 겸 오늘의 주제인(DFS, BFS)의 가장 쉬운 문제 일단 한번 시도해 보세요
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
*
1. DFS(깊이 우선 탐색)
2. BFS(너비 우선 탐색)
사실 그림만으로도 '어떤 느낌인지 알겠어!' 하겠지만 정확히는 이 둘의 차이를 이해하는게 중요하다
노드라는 말은 몰라도, '올바른 길 찾는 방식' 이라는건 이해가 가능할 것이라 생각하지만
문제별로 '올바른 길' 이 다르기 때문에 이 두 방식을 비교하면서 풀면 되겠다
공통 특 > 둘 다 모든 위치를 결국은 다 탐색한다
DFS 특 > 경로 별로 깊숙히 먼저 들어가기 때문에 경로의 특징이 남는다
BFS 특 > 가까운 곳부터 가기 때문에 그 때 그 때의 최선을 찾기 쉽다
앞선 지식을 바탕으로 오늘 제가 푼 문제는
https://school.programmers.co.kr/learn/courses/30/lessons/43163
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
class Solution {
static int min = 0;
static int count2 = 0;
public int solution(String begin, String target, String[] words) {
int answer = 0;
min = words.length + 1;
boolean[] useNum = new boolean[words.length];
getMin(begin, target, words, 0, useNum);
if(min == words.length + 1){
return 0;
}
else{
return min;
}
}
void getMin(String start, String target, String[] words, int getCount, boolean[] useNum)
{
boolean[] useNum2 = new boolean[useNum.length];
for(int i=0; i<useNum.length; i++){
useNum2[i] = useNum[i];
}
if(start.equals(target)){
System.out.println("equals 도달값 : " + getCount);
if(getCount < min){
min = getCount;
return;
}
}
getCount++;
for(int i=0; i<words.length; i++){
if(getDuplication(start, words[i])){
if(useNum2[i] == false){
System.out.println("duplication 통과 : " + words[i] + " " + getCount);
useNum2[i] = true;
getMin(words[i], target, words, getCount, useNum2);
}
}
}
}
boolean getDuplication(String a, String b)
{
boolean duplication = false;
int count = 0;
for(int i = 0; i<a.length(); i++)
{
if(a.charAt(i)==b.charAt(i)){
count++;
}
}
if(count==a.length()-1){
duplication = true;
}
return duplication;
}
}
구현하는 방식은 선행된 문제(네트워크)를 한번 풀어보고, 다른 사람이 푼 방식을 보면 알 수 있겠지만
DFS는 대체로 메서드를 재귀해서 불러내는 방식으로 구현한다.
-
우선 DFS로 풀 때의 문제점
1. 한번 사용한 숫자를 제외하고 다시 탐색해야 한다는 생각에 매번 배열 복사 (배열 자체를 넘기면 주솟값을 넘기는거니까 - 라는 생각에 매몰)
useNum[i] = true;
getMin(words[i], target, words, getCount + 1, useNum);
useNum[i] = false;> 간단하게, boolean값을 바꿔서 넘겨주고 같은 메서드 내에서는 상관 없도록 다시 바꿔서 for문을 돌게 하면 된다.
2. static(전역) 변수 쓸 필요 없음, 웬만하면 함수에서 return하는 방식으로 바꾸기
진짜 문제점
이 문제는 DFS로 푸는게 훨씬 복잡하고 오래 걸리는 방식이라는 점
문제에서도 키워드로 나와있지만, '가장 짧은 변환 과정 찾기' 즉 최단거리 구하는 방식이기 때문에 그 때 그 때 최선의 방식을 탐색하는 편이 좋다 = BFS
여기서 '큐' 개념을 먼저 알아야 하는데 간단히 설명하면 양쪽 면이 열린 긴 병에 바둑알을 넣는 형태의 '자료구조'
FIFO(FIRST IN FIRST OUT) 아마 정보처리기사/전공 공부를 조금이나마 해보셨다면 용어 자체는 알고 계실거라 생각한다. 사실 몰라도 말씀드린게 다인 개념이다
~는 개념적으로도 구현이 가능하고, 자바에서 제공한다. 메서드 문법은 필요할 때 마다 찾아서 공부하라지만 BFS를 구현하기에 아주 적합하니 쓰게 될 것이고(나도 몰랐다) 푸는 방식은 다음과 같다. 1
1. QUEUE에 (현재 단어, 원 단어에서 바뀐 횟수)를 쌍으로 해서 하나씩 넣는다
EX) 시작 단어: begin, 0(원단어)
2. 현재 들어있는 단어를 빼고 문제의 조건(한 글자만 바뀐 단어)에 맞는 단어를 넣는다
EX) (hot, 1)
3. 그것을 반복한다 (조건을 만족하는 단어가 1개가 아님을 기억하라, hot은 dot과 lot 모두 될 수 있음)
2회차 큐 내부 상태[("dot", 2), ("lot", 2)]
** 왼쪽이 먼저 들어와서 먼저 나가는 단어라고 생각하면 된다
3회차 큐 내부 상태 [("lot", 2), ("dog", 3)]
** dot에서 조건을 만족하는 다음 차례 단어 dog이 뒤로 들어옴
4-1. 반복하다보면 결국 최소 경로로 도달, 당시의 값이 최솟값
4-2 target 값에 도달하지 못함 = 0
** 최종 코드
import java.util.*;
class Solution {
public int solution(String begin, String target, String[] words) {
Queue<String> queue = new LinkedList<>(); // 탐색할 단어 저장
Queue<Integer> steps = new LinkedList<>(); // 변환 단계 저장
boolean[] visit = new boolean[words.length]; // 방문 기록
queue.offer(begin);
steps.offer(0);
while (!queue.isEmpty()) {
String current = queue.poll();
int step = steps.poll();
// 목표 도달
if (current.equals(target)) return step;
// 단어 리스트 탐색
for (int i = 0; i < words.length; i++) {
if (!visit[i] && isConvertible(current, words[i])) {
visit[i] = true; // 방문 처리
queue.offer(words[i]);
steps.offer(step + 1); // 변환 횟수 1 증가
}
}
}
// 도달 실패
return 0;
}
// 단어 갯수 차이 반환
boolean isConvertible(String a, String b) {
int diff = 0;
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) diff++;
if (diff > 1) return false; // 두 글자 이상 차이나면 false
}
return diff == 1;
}
}
~ Queue에 쌍으로 저장한다는 개념, 하나씩 넣었다 빼면서 최단 거리를 찾는다는 개념을 알면 관련된 문제는 풀 수 있을 것이다 ~