[level 3] Title: 단어 변환 파이썬

2022. 5. 30. 12:00·개인공부/알고리즘

 

 

DFS/BFS 유형문제로 나는 BFS를 사용하여 풀어보았다. BFS구현을 위해 deque를 사용하였다.

 

처음에는 입출력이 이해가 되질 않았다. 왜 "dot"을 거치는지 이해가 되질 않았는데 (사실 아직도 이해되지않는다..) 다른 블로그들을 참고하여, 문제를 풀기위한 방법으로 이해한 것은 한 번에 "한 개의 알파벳만 바꿀 수 있다" = "한개씩만 바꿀 수 있는경우 바꿔야한다." 라고 이해했다. 그리고 이 조건은 check 함수를 만들어서 조건으로 확인하였다.

 

queue에 들어가는 값은 단어와 변환횟수(cnt)를 담았고, 결국 target과  start가 일치 할 때, 현재 cnt에 + 1 을 반환하였다.

 

 

from collections import deque

def check(word, target):
    cnt = 0
    for a, b in zip(word, target):
        if a != b:
            cnt += 1
    return True if cnt == 1 else False

def solution(begin, target, words):
    if target not in words:
        return 0
    
    w = len(words)
    visited = [0] * w
    queue = deque([[begin, 0]])

    while queue:
        start, cnt = queue.popleft()
        for i in range(w):
            if check(words[i], start) and not visited[i]:
                if words[i] == target:
                    return cnt + 1
                visited[i] = 1
                queue.append([words[i], cnt + 1])
	return 0

 

 

코딩테스트 연습 - 단어 변환

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수

programmers.co.kr

 

728x90
저작자표시 (새창열림)

'개인공부 > 알고리즘' 카테고리의 다른 글

[level 3] Title: 숫자 게임 파이썬  (0) 2022.05.30
[level 3] Title: 가장 긴 팰린드롬 파이썬  (0) 2022.05.30
[level 3] Title: 가장 먼 노드 파이썬  (0) 2022.05.29
[level 3] Title: 순위 파이썬  (0) 2022.05.27
[level 3] Title: 최고의 집합 파이썬  (0) 2022.05.26
'개인공부/알고리즘' 카테고리의 다른 글
  • [level 3] Title: 숫자 게임 파이썬
  • [level 3] Title: 가장 긴 팰린드롬 파이썬
  • [level 3] Title: 가장 먼 노드 파이썬
  • [level 3] Title: 순위 파이썬
KEEMSY
KEEMSY
JUST DO IT
KEEMSY
목적, 수단, 목표
KEEMSY
전체
오늘
어제
  • 분류 전체보기
    • 회고
      • WIL
      • TIL
    • Project
    • 개인공부
      • 알고리즘
      • 아키텍처
      • 트러블슈팅
      • 테스팅
      • git
      • 배포

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

hELLO· Designed By정상우.v4.5.2
KEEMSY
[level 3] Title: 단어 변환 파이썬

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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