https://school.programmers.co.kr/learn/courses/30/lessons/43163
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
from collections import deque
def checkdiff(s1, s2):
n = 0
for i in range(len(s1)):
if s1[i] != s2[i]:
n += 1
if n > 1:
return 0
if n ==1:
return 1
def solution(begin, target, words):
if target not in words:
return 0
d = deque([[begin, 0]])
ans_l = []
while d:
d2 = d.popleft()
current, ans = d2[0], d2[1]
if current == target:
ans_l.append(ans)
continue
for i in range(len(words)):
if checkdiff(current, words[i]) == 1:
d.append([ words[i], ans + 1])
words[i] = "0"*len(current)
return min(ans_l)
문제를 정리해보자.
begin 과 target이 들어온다.
begin의 단어의 알파벳을 하나씩 바꿔가며, words 안에 있는 단어로 바꿔나간다.
begin이 target이 될 때까지의 최소 몇 번을 거치는가?
만약
begin = "hit", target = "cog" 인 경우
hit => hot => dot => dog => cog 의 단계를 거쳐 총 4번의 단계가 필요하다.
이 문제가 DFS 문제임을 알고, 풀어나가는 근거가 무엇일까?
https://mail-study.tistory.com/41
[백준] 21736번 : 헌내기는 친구가 필요해 [BFS 설명 有]
https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수
mail-study.tistory.com
위의 BFS 설명을 보면 BFS 에는 공통적인 특징이 있다.
1. 어느 점을 기준으로 좌표를 이동한다.
2. 이동하면 일련의 로직을 수행한 후 다음 좌표를 덱에 넣어준다. 이때 방문 정보 등 , 후 처리에 필요한 정보도 같이 넣어준다.
3. 방문한 좌표에 방문 처리를 해준다.
단어 변환 문제를 봐보자.
1. 한 번 바꾼 word는 다시 사용하지 않는다.
만약 hit => hot 으로 바꾼다면 hit 과 hot이라는 단어는 필요없다.
즉 한번 방문한 단어는 재사용하지 않는다.
각 단어의 길이는 3이상 10 이하이고, words의 단어는 50개 이하이다.
위의 제안사항을 보면 모든 경우를 다 들여다 봐도 시간 초과가 안 날 것임을 알 수 있다.
=> 문제는 우리가 모든 경우를 다 들여다보라는 것을 요구하고 있다는 것이다.
직관적으로 모든 경우를 보려면 당연히 words를 for문을 돌면서 모든 word를 방문해야 할 것이다.
이때 방문한 word는 방문 처리를 하면서 다음 경우를 찾아 나가야 한다.
2. 어느 점을 기준으로 좌표를 이동한다.
당연히 시작값인 begin을 기준으로 좌표를 이동할 것이다.
BFS는 그래프 문제만 있는 것이 아니다.
따라서 좌표라는 개념을 좀 더 포괄적으로 볼 필요가 있다.
bfs의 핵심은 좌표를 이동하는 것이 아닌, 가능한 모든 경우를 구하는 과정을
각 지점을 기준으로 순차적으로 해나가는 것이다.
설명이 두리뭉실하고 직관적이지 않을 것이다.
그림으로 보자아!
위의 그림을 보면 직관적으로 이해될 것이다.
각각의 루트는 당연하게도 한번 지나간 좌표는 다시 방문하지 않는다.
=> 방문 처리가 필요하다.
+++
각각의 루트에 대해서 좌표처리를 개별적으로 할 필요는 없다.
여기에서 중요한 부분이 또 나온다.
정답의 조건을 보자.
최소 루트의 단계의 수를 반환한다.
이 뜻이 무엇일까?
hit 부터 시작하면 단어를 하나씩 옮겨간다.
즉 현재의 좌표가 cog면 바로 현재까지의 단계의 개수를 반환하면 된다.
굳이 다른 루트까지 볼필요가 없기 때문이다.
위의 순서대로 트리를 타고 나갈 것이다.
만약 4번에서 target을 찾았다면?
굳이 10, 13번 까지 트리를 탈 필요가 있을까?
아니다!
만약 4번에서 target을 찾으면 target까지의 단계를 정답으로 return 해주면 된다!
따라서
words 의 값을 직접 참조하면서 words의 방문한 word를 "ㅒㅒㅒ" 등의 의미없는 데이터로 바꿔가며 방문처리를 하면 되는 것이다. (words의 값을 직접 바꿔나감 => 방문 리스트를 추가로 만들 필요X)
위의 문제에서는 words[i] = "0"*len(current) 로 "0"으로 단어를 바꿔 방문처리를 했다.
문제 조건에서 "모든 단어의 길이는 같다" 라는 조건을 주었기에 단어의 수만큼 "0" 이 필요하다.
위의 설명을 잘 읽어보면 이제 DFS 원리와 이 문제의 연결까지 이해가 될 것이다.
이제 부가적인 디테일을 알아보자!
문제를 풀기위해 필요한 기능들이 무엇이 있을까?
문제의 핵심적인 부분은 "알파벳을 하나씩 바꿔나간다" 는 부분이다.
그럼 직관적으로 두 단어가 알파벳 하나 차이인지 확인하는 기능이 필요할 것이다.
def checkdiff(s1, s2):
n = 0
for i in range(len(s1)):
if s1[i] != s2[i]:
n += 1
if n > 1:
return 0
if n ==1:
return 1
따라서 위 함수를 구현해서 깔끔하게 구현을 했다.
위처럼 함수화를 하면 문제를 작은 문제로 분할해서 하나씩 해나갈 수 있다.
추가로 이후 테스트하기에도 편리할 것이고, 중복을 피하므로 코드도 깔끔해진다.
정리해보자
중요한 부분이 무엇이었나...?
입력의 제한조건을 잘 보며 모든 경우를 다 살펴봐도 시간복잡도가 초과될지 생각해보자!
=> 정확하고 자세하게 할 필요 없다! 그냥 대충 봐서 될 것 같으면 DFS인가..? 생각할 수 있게 해보자!
문제가 어떤 정답을 요구하는 가에 따라 어떤 식으로 방문 처리를 해야 할 지 생각해보자!
=> 주어진 데이터를 직접 수정할지, 방문 저장 리스트나 그래프를 만들어서, 각각의 경우마다 넣어줄지..!
문제가 요구하는 핵심적인 로직을 어떻게 쉽게 짤 지 고민해보자!
=> 위의 경우처럼 함수화를 할수도 있고, 어떤식으로 코드를 짜면 좀 더 테스트하기 편하고, 직관적일지 고민해보자!
물론 이 글을 보고도 BFS 가 이해되지 않을 수 있다.
나도 당연히 BFS에 대해 완전히 이해하고 있지도 않고, 항상 어렵다고 느낀다.
항상 페이지를 들어가면 너무 장황한 설명과 글에 압도되어 집중을 하지 못했다.
하지만...!
위 글은 최대한 이해하기 쉽게 여러번 반복하고, 간단히 설명하도록 노력했다.
만약 위 글을 빨리 스크롤하면서, 이해하기 어렵다면...?
딱 한번만 처음부터 이 글을 다시 정독해보자!!
그래도 이해가 안된다면..
다른 글도 읽어보며 위 글을 참고하면 정말 이해할 것이라 생각한다!
파이팅임니다....! :)
'알고리즘 > 프로그래머스 문제풀이' 카테고리의 다른 글
| [프로그래머스] 베스트앨범[Level 3] (python 파이썬) (0) | 2024.04.25 |
|---|---|
| [프로그래머스] 여행경로 [Level 3] (python 파이썬) [BFS] (0) | 2024.04.21 |
| [프로그래머스] 징검다리 건너기 [Level 3] (python 파이썬) (0) | 2023.02.12 |
| [프로그래머스] 불량 사용자 [Level 3] (python 파이썬) (0) | 2023.02.11 |
| [프로그래머스] 메뉴 리뉴얼 [Level 2] (python 파이썬) (0) | 2023.02.08 |