해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 14226번 이모티콘 - BFS

www.acmicpc.net/problem/14226

문제 풀이

14226번 이모티콘 문제는 BFS로 풀 수 있는 문제입니다. 

2차 배열을 만들어 visit[화면에 있는 이모티콘][클립보드에 있는 이모티콘]에 걸린시간을 넣어주도록 합니다.

그리고 BFS 탐색을 할 때, (화면에 있는 이모티콘, 클립보드에 있는 이모티콘, 걸린 시간) 세트로  Queue에 넣어줍니다. 

BFS 탐색은 아래 문제에 있는 내용으로 하도록 합니다.

1.화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2.클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3.화면에 있는 이모티콘 중 하나를 삭제한다.

탐색을 종료하는 시점은 입력된 S의 값과 Queue에서 꺼낸 화면에 있는 이모티콘의 값과 일치하게 되면 걸린 시간을 반환하여 출력하도록 합니다. 

전체 코드

import sys
from collections import deque

def bfs() :
	visit = [[0]*2001 for _ in range(2001)]
	queue = deque()

	# ( screen, clipboard, time)
	queue.append((1, 0, 0))

	result_m = 987654321

	while queue:
		sS,sC,sT = queue.popleft();

		if sS == S:
			result_m = min(result_m, sT)
			break

		nT = sT + 1
		nC = sS
		# 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장
		#print("sS = ", sS, ", sC = ", sC, ", sT = ", sT, ", nT = ", nT, ", nC = ", nC)

		if 0 < sS <=1000 and (visit[sS][nC] > sT or visit[sS][nC] == 0):
			visit[sS][nC] = nT
			queue.append((sS, nC, nT))

		# 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
		nS = sS + sC
		#print("sS = ", sS, ", sC = ", sC, ", sT = ", sT, ", nT = ", nT, ", nC = ", nC, ", nS = ",nS)
		if nS <= 2*S and (visit[nS][sC] > sT or visit[nS][nC] == 0):
			visit[nS][sC] = nT
			queue.append((nS, sC, nT))

		#화면에 있는 이모티콘 중 하나를 삭제한다.
		nS = sS - 1
		if sS -1 > 0 and (visit[nS][sC] > sT or visit[nS][nC] == 0):
			visit[nS][sC] = nT
			queue.append((nS, sC, nT))

	return result_m

S = int(input())
result = 0
result = bfs()
print(result)