이것이 코딩 테스트다 PART3 with python : DFS/BFS

18. 괄호 변환 ( 난이도 1 )

def dfs(p):
  if not p:  
    return ""

  left = 0
  right = 0
  for i in range(len(p)):
    if "(" == p[i]:
      left += 1
    else: right += 1

    if right == left:
      u = p[:i+1]
      v = p[i+1:]
            
      #4 u: 균형잡힌 문자열
      if u[0] == ")" or u[-1] == "(":
        sentence = "("

        if dfs(v) is not None:
          sentence += dfs(v)
        sentence += ")"

        for j in u[1:-1]:
          if j =="(":
            sentence += ")"
          else:
            sentence += "("
        return sentence

      #3 u: 올바른 문자열
      else:
        return u + dfs(v)

dfs("()))((()")
#예 1 : (()())()			출력: (()())()
#예 2 : )(				    출력: ()
#예 3 : ()))((()			출력: ()(())()

15. 특정 거리의 도시 찾기( 난이도 1.5 )

나의 솔루션

from collections import deque

# n: 도시개수, m : 도로개수, k : 최단거리, x:출발도시
n , m , k, x = map(int,input().split())

graph=[]
for i in range(m):
  graph.append(list(map(int,input().split())))

# 거리 0으로 초기화
distance = [0] * n

def bfs(start):
  queue = deque()
  subqueue = deque()
  
  # 출발지
  xpoint_start = [item for item in graph if x == item[0]]

  for s in xpoint_start:
    queue.append(s)

    while queue:
      data = queue.popleft()
      start = data[0]
      end = data[1]
      
      # 거리 업데이트
      distance[end-1] = 1 + distance[start-1]      
      # 연결된 도로 찾기
      indexs = [index for index, item in enumerate(graph) if item[0] == end]
      
      # 연결된 도로가 있다면 서브큐에 저장
      if indexs: 
        for idx in indexs:
          subqueue.append(graph[idx])
          
	  # 서브큐의 도로를 메인큐로 이동
      if subqueue:
        queue.append(subqueue.popleft)


  # 최단거리가 k인 도로 찾기
  results = [index for index, item in enumerate(distance) if item == k]

  if results:
    for result in results:
      print(result+1)
  else:
    print(-1)
  
  
bfs(x)

답안

from collections import deque
n,m,k,x = map(int,input().split())

#도로 정보 초기화
graph=[[] for _ in range(n+1)]

for _ in range(m):
  a,b = map(int, input().split())
  graph[a].append(b)
  # a : 출발지, b: 도착지

#최단 거리 초기화
#distance: 출발도시에서 다른도시까지 걸리는 거리
distance = [-1] * (n+1)
distance[x] = 0 #출발도시까지 거리 초기화

# BFS
q = deque([x])

while q:
  now = q.popleft()
  # next_node: now에서 도착할 수 있는 도시번호
  for next_node in graph[now]:
    # 아직 방문하지 않은 도시
    if distance[next_node] == -1:
      distance[next_node] = distance[now] + 1
      q.append(next_node)

check = False
for i in range(1,n+1):
  if distance[i] == k:
    print(i)
    check = True

if check == False:
  print(-1)

17. 경쟁적 전염

from collections import deque

# n:시험관 크기, k:바이러스 종류 수
n, k = map(int,input().split())

graph = []

for _ in range(n):
  row = list(map(int,input().split()))
  graph.append(row)

# 초 , 행, 열
s, target_x, target_y= map(int,input().split())

# 시간, 바이러스종류, 행, 열
initPointer = [[0, graph[x][y],x, y] for x in range(n) for y in range(n) if graph[x][y] != 0]
initPointer.sort()

queue = deque(initPointer)

#상하좌우
dy=[-1,1,0,0]
dx=[0,0,-1,1]

while queue:
  t, virus, x, y = queue.popleft()
 
  if t == s:
    break;
  for i in range(4):
    ny = y + dy[i]
    nx = x + dx[i]

    if(ny >= n or nx >= n or nx < 0  or ny < 0 ):
      continue
    else:
      if graph[nx][ny] == 0:
        graph[nx][ny] = virus
        queue.append([t+1,virus, nx,ny])

print(graph[target_x-1][target_y-1])