[Python][백준 1897] 토달기

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

1897번: 토달기

---

/*
신경써야 할 부분은 바로 :
1. 토달기 가능한 단어가 없을 시 시작한 단어가 정답
2. bfs 로 탐색하며 확인해야 하는 조건들 : 
	- 토달기 단어보다 한글자 많아야 한다.
    - 토달기 단어를 포함하는 단어 
    - 중간에 다른 글자 하나를 포함한 토달기 단어
    	- 투 포인터로 문자열 탐색
    - 방문 처리를 통해 방문한 단어 재방문 방지
    
어려워 보이지만 방법 자체만 알면 그리 어렵진 않다
*/

---

import sys
from collections import deque
input = sys.stdin.readline
 
def checkMid(word, target_word):
    target_word_idx = 0
    word_idx = 0
    while word_idx < len(word):
        if word[word_idx] == target_word[target_word_idx]:
            target_word_idx += 1
        word_idx += 1
    if target_word_idx == len(target_word):
        return True
    else : 
        return False
    

def bfs(start):
    global result 
    visited = []
    queue = deque([start])
    visited.append(start)

    while queue:
        target = queue.popleft()
        for word in words:
            if word in visited or len(word) - 1 != len(target) :
                continue
            if word[1:] == target or target == word[:-1] or checkMid(word,target):
                queue.append(word)
                visited.append(word)
                result = word
          
n, start = input().split()
n = int(n)
words = [input().rstrip() for _ in range(n)]
result = start

bfs(start)
print(result)

---

풀 때 어려웠던 점 또는 느낀점 :

공익 PS 4일차

분명 다 풀었는데 "틀렸습니다" 가 떠서 당황했다

알고보니 토달기 가능한 단어가 사전에 없을 시

시작 단어가 정답으로 인정된다는 것을 확인했다.

그리고 중간에 다른 글자가 하나 포함되어 있는지

확인하는 코드도 오류가 많이 났다. 

좀 더 꼼꼼하게 짜야겠다.

 

---

참고할만한 다른 사람 코드 :

import sys


def check(x):
	global ans

	for i in range(len(x)):
		n = x[:i] + x[i + 1:]
		if n in words and words[n]:
			words[x] = True
			if len(x) > len(ans):
				ans = x
			return


N, word = sys.stdin.readline().split()
words = { sys.stdin.readline().rstrip(): False for _ in range(int(N)) }
words[word] = True
ans = word
for x in sorted(words, key=lambda x: len(x)):
	check(x)
print(ans)

 

위의 코드는 길이를 기준으로 정렬 후

글자를 하나씩 빼가며 해당 글자가 사전에 있는 확인하는 식으로 구현했다

확실히 코드 길이가 짧아 읽기 편하고 시간도 많이 절약했다.

방문 처리를 words 라는 딕셔너리를 통해 시간 절약을 잘한것 같다.