Early Riser
생각정리
Early Riser
전체 방문자
오늘
어제
  • 분류 전체보기 (117)
    • JS (14)
    • React (28)
    • React Native (4)
    • Library, Tool (12)
    • Algorithm (40)
    • Computer Science (3)
    • 회고 (3)
    • AI (13)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기

공지사항

인기 글

태그

  • 오늘의불경
  • 알고리즘
  • 백준
  • react
  • 완전탐색
  • global minima
  • LGBM
  • local minima
  • useEffect
  • BFS
  • 파이썬
  • dfs
  • 프로그래머스
  • 구현
  • 밑바닥
  • 딥러닝
  • 논문리뷰
  • 부스트캠프 합격 후기
  • RNN
  • 불경앱
  • js
  • 비동기
  • lightgbm
  • useState
  • 손실함수
  • 자바스크립트
  • javascript
  • 부스트캠프 9기
  • 백트래킹
  • boosting

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Early Riser
Algorithm

프로그래머스: 단어 변환 (파이썬, BFS)

프로그래머스: 단어 변환 (파이썬, BFS)
Algorithm

프로그래머스: 단어 변환 (파이썬, BFS)

2022. 12. 14. 16:44

변환 횟수가 최소인 경우를 구해야 하므로 BFS로 접근하였다. 처음에 단어들을 어떻게 그래프로 표현할까 하다가 변환 경우의 수를 그려보니 굳이 그래프로 표현 안해도 풀 수 있다는 생각이 들었다. 

 

처음에 테스트케이스3에서 계속 틀렸었는데 그 이유는 두 단어간에 다른 알파벳 갯수를 셀 때 set을 이용해 세었기 때문이다. 그럼 'ccec'같은 단어는 'ce'가 되므로 적절한 비교가 이루어지지 않음을 알 수 있다. 아직 엣지케이스를 생각하는 능력이 부족한 것 같아 그 부분에 대해 좀 더 훈련이 필요하겠다..

 

풀이 코드는다음과 같다. BFS는 넓이를 우선으로 탐색하므로 처음에 begin과 차이가 1인 단어들을 deque에 넣고 그 단어들에 대해 다시 차이가 1인 단어들을 deque에 넣으면 넓이 우선 탐색으로 탐색이 잘 되는 것을 볼 수 있다.

from collections import deque


def difference(word1, word2):
    word2 = list(word2)
    for word in word1:
        if word in word2:
            del word2[word2.index(word)]
    return len(word2)


def solution(begin, target, words):
    if target not in words:
        return 0
    else:
        visited = [False for _ in range(len(words))]
        queue = deque([(begin, 0)])
        while queue:
            cash = queue.popleft()
            if cash[0] == target:
                return cash[1]
            for j in range(len(words)):
                diff = difference(cash[0], words[j])
                if diff == 1 and not visited[j]:
                    queue.append((words[j], cash[1] + 1))
                    visited[j] = True

'Algorithm' 카테고리의 다른 글

프로그래머스: 가장 먼 노드(파이썬, BFS)  (0) 2022.12.15
프로그래머스: 여행 경로 (파이썬, DFS, 백트래킹)  (0) 2022.12.15
프로그래머스: 네트워크 (파이썬, DFS)  (0) 2022.12.14
프로그래머스: 게임 맵 최단거리(파이썬, DFS, BFS)  (0) 2022.12.14
프로그래머스: 햄버거 만들기(파이썬, 스택)  (0) 2022.12.05
    'Algorithm' 카테고리의 다른 글
    • 프로그래머스: 가장 먼 노드(파이썬, BFS)
    • 프로그래머스: 여행 경로 (파이썬, DFS, 백트래킹)
    • 프로그래머스: 네트워크 (파이썬, DFS)
    • 프로그래머스: 게임 맵 최단거리(파이썬, DFS, BFS)
    Early Riser
    Early Riser
    1년차 프론트엔드 개발자입니다. https://github.com/EarlyRiser42

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.