2023 팀네이버 신입 공채 준비 (10) 프로그래머스 DFS/BFS

오늘 한 리스트

1. 프로그래머스 DFS/BFS 3문제

프로그래머스 DFS/BFS 게임 맵 최단거리

• 문제 유형 : DFS/BFS
  최단거리

  from collections import deque
  def solution(maps):
    y_axis=len(maps)
    x_axis=len(maps[0])
      
    st=deque([(0,0,1)]) # 시작 지점
      
    move = [[1,0],[-1,0],[0,-1],[0,1]]
      
    while st:
        x,y,d=st.popleft() # 가장 먼저 넣은 것 부터 해결
        print(x,y)
        for i in move: # for문을 쓰기 때문에 x,y값 변겨돰
            nx=x+i[1]
            ny=y+i[0]
            if -1<nx<x_axis and -1<ny<y_axis:
                if maps[ny][nx]==1 or maps[ny][nx]>d+1: # 더 큰 경우의 수가 나올 경우 작은 경우의 수로 줄여줌
                    maps[ny][nx]=d+1
                    if ny==y_axis-1 and nx==x_axis-1:
                        return d+1
                      
                    st.append((nx,ny,d+1))
    return -1
  

  이 코드도 도저히 모르겠어서 다른 사람의 소스코드를 참고해서 풀어낸 정답이다.

프로그래머스 DFS/BFS 단어 변환

• 문제 유형 : DFS/BFS
  단어 변환

  from collections import deque
  def solution(begin, target, words):
    if not target in words:
        return 0
    test=[0]*len(words)
    visited=[False]*len(words)
    st_word=deque([(begin,0)])
    while st_word:
        f_word,d=st_word.popleft()
        for n,word in enumerate(words):
            for i in range(len(word)):
                if word[:i]+word[i+1:] == f_word[:i]+f_word[i+1:]:
                    if visited[n]==True:
                        continue
                    test[n]=d+1
                    visited[n]=True
                    st_word.append((word,d+1))
    #print(words.index(target))
    return test[words.index(target)]
  

  이건 직접 풀어낸 코드이며 각 단어에 해당하는 list를 만들고 d를 만들어 위코드와 유사하게 풀었다.

프로그래머스 DFS/BFS 여행경로

• 문제 유형 : DFS/BFS
  여행경로

  # 사용한 index를 같이 넣어줌
  from collections import deque
  def solution(tickets):
    st=deque([("ICN",[])])
    answer=[]
    while st:
        #print(st)
        s_point,index_list=st.popleft()
        if len(index_list)==len(tickets):
            answer.append(index_list)
            continue
        #print(s_point,index_list)
        for num,ticket in enumerate(tickets):
            if ticket[0] == s_point:
                #print(ticket[0])
                if num in index_list:
                    continue
                #index_list.append(num)
                st.append((ticket[1],index_list+[num]))
    #print(answer)
                  
                  
    final_answer=["ICN"]
    if len(answer)>1:
        check_index=[]
        for num in answer:
            wwords=""
            for j in num:
                wwords+=tickets[j][1]
            check_index.append(wwords)
        ck_i=check_index.index(min(check_index))
        for i in answer[ck_i]:
            final_answer.append(tickets[i][1])
    else:
        for i in answer[0]:
            final_answer.append(tickets[i][1])
              
    return final_answer
  

  조금 오래 걸린 문제긴 한데 deque에 index_list를 같이 넘어줌으로써 모든 경우의 수를 담을 수 있도록 만든 코드이다.