[백준]9177 단어섞기

1. 풀이

일반적인 많이풀던 (grid) bfs문제와 비슷한데 index처리를 너무못해서 너무 오래 걸렸다.

처음에는 visited를 고려해주지 않아서 메모리초과(시간초과)가 났다 ((1)메모리초과, visited사용x)

모든 경우의 수를 다 따져주어야 한다고 생각했지만, 

a=acs , b=acbs , c=acacbss 일때 아래의 두 경우는 같은 경우이기 때문에 visited로 관리해줘서 한가지 경우만 탐색해 주어야 시간을 줄일 수 있다. ((2)통과)

<1번경우>

a c s

1 2

a c b s

3 4


<2번경우>

a c s

3 4

a c b s

1 2

이후 vistied를 사용해서 큐를 구성할 때 인덱스 에러가 많이 났다.

(1) 다음 방문지를 기준으로 q에 넣을 수 있는지 검사하고(aIndx+1<sizeA)

(2) visited를 검사 해주는(visited[aIndx+1][bIndx]

원칙을 (grid에서 tempR,tempC를 검사하는것처럼) 지켰어야 했는데, 그러면 시작 aIndx와 bIndx를 -1로 초기화 해야되기 때문에 visited리스트에 넣기 힘들거같아서 다른방법으로 했다.

하지만 위의 문제는 그냥 visited의 행과 열을 +1씩 해주고 인자로 넣을때도 aIndx+1, bIndx+1을 넣어서 쉽게 해결할 수 있는 문제였다. (visited[aIndx+2][bIndx+1])

 

2. 소스코드

(1) 메모리초과, visited사용x

from collections import deque
T=int(input())
for t in range(T):
    a,b,c=input().split()
    sizeA=len(a)
    sizeB=len(b)
    sizeC=sizeA+sizeB
    q=deque([["",0,0,0]])
    ans="no"
    while(q):
        nowWord,aIndx,bIndx,size=q.popleft()
        if size==sizeC:
            ans="yes"
            continue
        #A를 추가하기
        if aIndx<sizeA and c[size]==a[aIndx]:
            q.append([nowWord+a[aIndx],aIndx+1,bIndx,size+1])
        if bIndx<sizeB and c[size]==b[bIndx]:
            q.append([nowWord+b[bIndx],aIndx,bIndx+1,size+1])

    print("Data set %d: %s"%(t+1,ans))

 

(2) 통과

import sys
from collections import deque

T=int(input())
for t in range(T):
    a,b,c=sys.stdin.readline().rstrip().split()
    sizeA=len(a)
    sizeB=len(b)
    sizeC=sizeA+sizeB
    ans="no"
    visited=[[0 for j in range(sizeB+1)] for i in range(sizeA+1)]
    q = deque([["",-1,-1,0]])
    visited[0][0]=1
    while(q):
        nowWord,aIndx,bIndx,size=q.popleft()
        if size==sizeC:
            ans="yes"
            break
        if aIndx+1<sizeA and c[size]==a[aIndx+1] and visited[aIndx+2][bIndx+1]==0:
                q.append([nowWord+a[aIndx],aIndx+1,bIndx,size+1])
                visited[aIndx+2][bIndx+1]=1
        if bIndx+1<sizeB and c[size]==b[bIndx+1] and visited[aIndx+1][bIndx+2]==0:
                q.append([nowWord+b[bIndx],aIndx,bIndx+1,size+1])
                visited[aIndx+1][bIndx+2]=1
    print("Data set %d: %s"%(t+1,ans))