2252 줄 세우기(insert 와 append의 시간효율성)

2252번: 줄 세우기 (acmicpc.net)

#topological algorithm(위상정렬)

2252번: 줄 세우기

#topological algorithm

 

위상정렬과 dfs의 가장 큰 차이점은 출력을 하고 다른 인접한 정점을 확인하느냐 아니면 모든것을 스택에 넣고 그 스택

 

을 한번에 출력하느냐 이다. 우선 위상정렬은 스택을 이용하여 한번에 내보내는 방식이다. visited 리스트와 재귀를 이용

 

하여 스택에 순서대로 정리를 해야한다. 반면 dfs는 스택을 이용하지 않고 재귀를 사용하는데 하나씩 출력해주고 그다음

 

바로 재귀를 돌리는 형식이다. 이는 dfs는 시작하는 값을 알려줘서 그 초기값 기준으로 선후관계가 다양하지않고 한 방

 

향으로 배열을 만들기 때문에 가능하다고 생각한다. 여기서 시간효율성을 더 올리는 방법은 incoming이 없는 정점을 선

 

택하여 먼저 돌리는 것이다. 밑의 코드에서는 이 정점을 선택하여 돌리는 코드를 포함하고 있다.

 

#### 9/1 업데이트 ####

 

dfs와 topological algorithm 의 가장 큰 차이는 dfs는 선후 관계를 따지는 알고리즘이 아니라는 것. 이는 무슨 말이냐면 초기 값만 정해져있을뿐 나머지는 그것을 기준으로 연결된 간선을 찾는 것이지 1 2 이렇게 되어 있다고 무조건 1이 2보다 먼저 가야된다는 것은 아니라는 것이다.

 

#내가 본 답지

from sys import stdin

 

input=stdin.readline

#스탠다드 인풋 시간 효율성을 위해

n,m=map(int,input().split())

#n,m 입력

mapp=[[] for key in range(n+1)]

primes=[False]* (n+1)

#이 정점이 income이 있는가 없는가

for _ in range(m):

a,b=map(int,input().split())

mapp[a].append(b)

primes[a],primes[b]=True,False

#mapp에는 vertex prime은 income이 있다면 False 로 만듬

vstd=[False] * (n+1)

#스택에 인덱스값이 있는가 없는가

answer=[]

#답(스택)

def dfs(x):
vstd[x]=True

#해당 인덱스값을 True로 만들고
if mapp[x]:

#vertex가 존재한다면
for nxt_node in mapp[x]:

if not vstd[nxt_node]:
dfs(nxt_node)

#만약 그 vertex에 해당값이 False라면 이것을 재귀 ( 새로운 조건이 추가된다는 느낌)
answer.append(x)

#스택에 입력

for i in range(1,n+1):
if primes[i] and not vstd[i]:

#income도 없고 스택에도 없는 인덱스 찾아서
dfs(i)

#dfs
for i in range(1,n+1):
if not vstd[i]:
answer.append(i)

#vertex에 없었던 애들 그냥 스택에 넣음

answer.reverse()

#append이기 때문에 거꾸로 바꿔줘야함
print(" ".join(map(str,answer)))

 

#답지를 본 이유는 코드 자체가 틀리진 않았었지만 시간이 다른 사람들의 코드에 비해서 더 걸려보였다. 이유를 찾아보니 두가지로 가설을 세웠다.

 

1. Primes 로 for문을 두번 돌긴 하지만 더 효율적으로 되어 빨랐을것이다.

 

2. 기타의 이유

 

1로 예상을 했었지만 결국 2로 밝혀지게 되었다. 이유는 간단했다. insert와 append의 시간효율성 차이였다. insert는 인

 

덱스 0을 탐색하여 i를 집어넣는 함수라 그런지 append보다 더 오래걸렸고 이는 200ms의 차이를 보였다. 고로 원래의

 

코드에서 insert를 append로 바꾸고 reverse화 시키는 선택과 dps중간에 for문을 돌릴때 graph[i]가 없으면 for문에 입장

 

하지 않는 코드를 추가하여 효율성을 극대화 했다.

 

#내가 짠 코드

from sys import stdin

from collections import defaultdict

input=stdin.readline

n,m=map(int,input().split())

graph=defaultdict(list)

visited=[False]*(n+1)

for i in range(m):

u,v=map(int,input().split())

graph[u].append(v)

def topologicalSortUtil(v,visited,stack):

visited[v]=True

for i in graph[v]:

if visited[i]==False:

topologicalSortUtil(i,visited,stack)

stack.append(v)

def topologicalSort(v):

for i in range(1,n+1):

if visited[i]==False:

topologicalSortUtil(i,visited,stack)

stack=[]

for i in range(1,n+1):

if visited[i]==False:

topologicalSort(i)

stack.reverse()
print(' '.join(map(str,stack)))

 

# *stack으로 마무리 할 수있었지만 크기 때문인지 ' '.join(map(str,stack))으로 하는게 이 코드에서는 더 빨랐다. 여기까지

 

topological algorithm 이였다. 여기서 배운건 dps와 topological algorithm class __init__ self 등등 많은걸 알아가고 구글

 

링을 통해 영어가 프로그래밍에서 얼마나 중요한 언어인지를 알게 되었다. 좀더 열심히 해보자