백준 1260 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.

해당 부분 지적 감사히 받습니다.

 

문제부터 보자

문제를 봤다.

 

이제야 알고리즘에 한발 다가서는구나 생각 들었다.

 

머지않아, 내가 달을 보며 걷고 있구나라고 생각했다.

 

시간은 오래 걸렸지만, 스스로 구현했다.

코드

import sys

sys.setrecursionlimit(10**6)

from collections import deque

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

array=[[]for i in range(n+1)]

visit=[]

for i in range(m):

    a = input().split()

    array[int(a[0])].append(int(a[1]))

    array[int(a[1])].append(int(a[0]))

   

for i in array:

    i.sort()

   

def dfs(v):    

    if(v not in visit):

        print(v,end =' ')

        visit.append(v)

        for i in range(len(array[v])):

            dfs(array[v][i])

           

def bfs(v):

    if(v not in visit):

        print(v,end = ' ')

        visit.append(v)

        for j in range(len(array[v])): # 0, 1

            if(array[v][j] not in visit):

                visit.append(array[v][j]) # 3,0   3,1

                print(array[v][j],end = ' ')

    if(len(visit)==n):

        return

    bfs(array[v][0])

               

dfs(v)

visit.clear()

print('')

bfs(v)

 

아. 재귀함수 호출 제한 풀어주는 건 검색했다.

 

결과는

메모리 초과란다.

 

첫 제출에 정답은, 다른 사람의 코드를 그대로 가져다 썼다.

 

왜 그랬냐라고 물어보면 이 문제의 티어를 보고 싶었다.

 

지금 생각해 보니 그냥 검색해 볼걸 하고 생각 든다.

 

메모리 초과를 봤을 때, 또 좌절을 느꼈다.

 

곧 다시, 해야겠다 생각만 했던 시간복잡도, 메모리에 대해 공부할 명분이 생겨 다행이라 생각이 들었다.

 

마음이 급해 시작하지 못하고 있었는데, 다시 돌아갈 계기가 되었다.

 

그리고 정답 코드는 다른 사람의 코드를 첨부해 올리겠다.

 

코드

from collections import deque

def dfs(start):

    visited[start] = True

    print(start, end=" ")

    for i in graph[start]:

        if not visited[i]:

            dfs(i)

def bfs(start):

    queue = deque([start])

    visited[start] = True

    while queue:

        v = queue.popleft()

        print(v, end=" ")

        for i in graph[v]:

            if not visited[i]:

                visited[i] = True

                queue.append(i)

N, M, V = map(int, input().split())

graph = [[] for _ in range(N + 1)]

for _ in range(M):

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

    graph[a].append(b)

    graph[b].append(a)

# 정렬

for i in graph:

    i.sort()

# dfs

visited = [False] * (N + 1)

dfs(V)

print()

# bfs

visited = [False] * (N + 1)

bfs(V)

 

어우 색깔 입혀지니 멋있네

 

앞으로 내 코드도 이렇게 올려야 하나..?

 

수정했다 ㅋㅋ 앞으로 이렇게 올려야지

 

 

++++++++++++++++++++++++++++++++++++++++추가++++++++++++++++++++++++++++++++++++++++++++++++

 

마음이 너무 찝찝해 다시 공부하고 완벽히 이해하여 내용을 추가한다.

 

코드

 

from collections import deque

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

array=[[]for i in range(n+1)]

visit=[False]*(n+1)

for i in range(m):

    a = input().split()

    array[int(a[0])].append(int(a[1]))

    array[int(a[1])].append(int(a[0]))

for i in array:

    i.sort()

   

def dfs(v):    

    visit.append(v)

    print(v,end =' ')

    for i in range(len(array[v])):

        if(array[v][i] not in visit):

            dfs(array[v][i])

print(array)

def bfs(v):

    queue = deque([v])  # 시작 정점을 큐에 넣음

    visited = [False] * (n + 1)  # 정점의 방문 여부를 저장하는 리스트

    visited[v] = True  # 시작 정점을 방문했음을 표시

    while queue:  # 큐가 빌 때까지 반복

        node = queue.popleft()  # 큐의 가장 왼쪽(맨 앞)에 있는 정점을 꺼냄 ,3

        print(node, end=' ')  # 방문한 정점을 출력 ,3

        for neighbor in array[node]:  # 현재 정점에 연결된 모든 이웃 정점들에 대해

            if not visited[neighbor]:  # 이웃 정점을 방문하지 않았다면

                queue.append(neighbor)  # 큐에 이웃 정점을 추가하여 나중에 방문

                visited[neighbor] = True  # 이웃 정점을 방문했음을 표시

               

dfs(v)

visit.clear()

print('')

bfs(v)

이제야.. 드디어 이해가 되었다.

 

나는 최대한 라이브러리 함수 없이 직접 구현해서 사용하는 것을 좋아한다.

 

또한 남들이 일반적으로 생각해내는 방법보다, 내가 생각해 낸 방법대로 완성시키는 데에 큰 의미를 둔다.

 

하지만 코딩테스트를 위한 공부에서는, 나의 신념이 독이 될수 있다는 것을 느꼈다.

 

그래서 접어두고 받아들인다.

 

지금 중요한건 신념이 아니라, 능력이다.

 

출처 : https://ji-gwang.tistory.com/291

백준 1260번 파이썬 문제풀이(큐와 그래프 - DFS와 BFS)

 

배운 점

1. 필요하다고 생각 드는 건 필요하기 때문이다.

2. popleft() 큐의 가장 왼쪽 요소를 꺼낸다. // ex) a= [1,2,3,4]  v = popleft(),  print(v) = '1'

3. queue = deque([n]) // 큐에 n을 넣는다.