[til] 220305 | deque, dfs

2022. 3. 6. 00:46Algorithm

[deque (python)]

 

백준 #10866 덱:

 

계속 시간초과가 나옴 ㅠ 제한시간 0.5초

ord=input()
if "push_front" in ord:
    num_index=ord.find(' ')
    num=int(ord[num_index+1:])
    queue.appendleft(num)

처음엔 input()을 split()할 생각을 못함.

왜? push_front, push_back 외에는 그냥 한 덩어리(?)로 끝나니까 split() 할게 없다고 생각해서..

근데 그냥 상관없는 거였다.

 

아무튼 그래서 split()하고 좀 더 간결하게 만들었는데:

ord=input().split()
if "push_front" in ord:
    queue.appendleft(ord[1])

역시 시간초과.

 

결국 구글링해서 찾아보니까 input()으로 받는게 아니라 sys.stdin.readline() 으로 받아와야 한다..

시간이 더 빠름.

최종 답:

#10866 덱
from collections import deque
import sys

n=int(sys.stdin.readline())
queue=deque()
for _ in range(n):
  ord=list(sys.stdin.readline().split())
  if "push_back" in ord:
    queue.append(ord[1])
  if "push_front" in ord:
    queue.appendleft(ord[1])
  if ord[0]=="front":
    if len(queue)>0:
      print(queue[0])
    else:
      print(-1)
  if ord[0]=="back":
    if len(queue)>0:
      print(queue[-1])
    else:
      print(-1)
  if ord[0]=="size":
    print(len(queue))
  if ord[0]=="empty":
    if len(queue)>0:
      print(0)
    else: print(1)
  if ord[0]=="pop_front":
    if len(queue)>0:
      a=queue.popleft()
      print(a)
    else:
      print(-1)
  if ord[0]=="pop_back":
    if len(queue)>0:
      a=queue.pop()
      print(a)
    else:
      print(-1)

* deque로 큐를 만들 때 큐에서 앞, 뒤가 각각 왼쪽인지 오른쪽인지 헷갈렸는데

정리하자면,

큐의 앞: 덱의 왼쪽

큐의 뒤: 덱의 오른쪽

따라서 큐의 앞에 원소를 넣는다 하면 deque.appendleft(*) 를 쓰고

큐의 뒤에 넣는다 하면 deque.append(*)를 쓰면 된다.

 

* 참고로 deque 라이브러리는 큐를 사용할 때만 유용하고 스택이나 다른 자료구조를 구현할 때는 그냥 list를 쓰면 된다고 한다.

큐는 앞, 뒤 모두 접근이 가능해야하는데 deque가 popleft(), appendleft() 메소드가 있기 때문에 리스트를 다 훑지 않고도 바로 접근이 가능하기 때문에 시간이 더 빠르기 때문.

 


 

[dfs,bfs (또) 복습]

백준 #2606 바이러스

- 여태 풀었던 문제들 중에선 풀기 그나마 쉬운 편이었다..

- 근데 아직 언제 dfs를 쓰고 언제 bfs를 쓰는지 감이 크게 오지는 않는다.. 일단 bfs는 최단거리에 쓰는 건 알겠는데,, 다시 복습해야겠다

- 이 문제에선 dfs일 것 같아서(?) dfs로 우선 풀어봤고, bfs도 풀어봤는데 시간은 dfs로 푸는 게 더 빠르다.

위에가 dfs로 푼거, 아래가 bfs로 푼거

DFS:

#2606
cnt_computers=int(input())
connected=int(input())
graph=[[] for i in range(cnt_computers+1)] #인덱스 숫자 맞춰주기 위해 +1
visited=[False]*(cnt_computers+1)
for _ in range(connected):
  a,b=map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

def dfs(graph, v, visited):
  visited[v]=True
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

dfs(graph,1,visited)
a=visited.count(True)-1 #1번 컴터 제외
print(a)

BFS:

#2606
cnt_computers=int(input())
connected=int(input())
graph=[[] for i in range(cnt_computers+1)] #인덱스 숫자 맞춰주기 위해 +1
visited=[False]*(cnt_computers+1)
for _ in range(connected):
  a,b=map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

from collections import deque
def bfs(graph,start,visited):
  dq=deque([start])
  visited[start]=True
  while dq:  #덱이 빌 때까지
    v = dq.popleft() 
    for i in graph[v]:
      if not visited[i]:
        dq.append(i)
        visited[i]=True

bfs(graph,1,visited)
a=visited.count(True)-1
print(a)