[CLASS 3]백준 1260번, 1541번

1260번 : DFS와 BFS

 

BFS와 DFS를 구현할 수 있느냐? 를 묻는 문제이다. 쉽게 풀 수 있을 터..인데..

 

내 코드(시간 초과):

import sys
from collections import deque
input = sys.stdin.readline

n,m,root = map(int,input().split())
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    i,j = map(int,input().split())
    nodes[i].append(j)
    nodes[j].append(i)

for i in range(len(nodes)):
    nodes[i].sort()

def dfs(start,n):
    visited = [False] * (n+1)
    stack = []
    answerli = []

    visited[start] = True
    answerli.append(start)
    stack.append(start)
    while stack:
        for idx,node in enumerate(nodes[stack[-1]]):
            if not visited[node]:
                # 방문 처리
                visited[node] = True
                answerli.append(node)
                stack.append(node)
                break
            # 주변 노드가 모두 방문되었다면
            if idx == len(nodes[stack[-1]]) - 1:
                stack.pop()
    
    return answerli

def bfs(start,n):
    visited = [False] * (n+1)
    queue = deque()
    answerli = []

    visited[start] = True
    answerli.append(start)
    queue.append(start)
    while queue:
        now = queue.popleft()
        for node in nodes[now]:
            if not visited[node]:
                # 방문 처리
                visited[node] = True
                answerli.append(node)
                queue.append(node)

    return answerli



print(' '.join(map(str,dfs(root,n))))
print(' '.join(map(str,bfs(root,n))))

처음엔 이걸 작성하고 잘 구현했다! 라고 생각했지만 시간 초과에 걸려버렸다. 그 이유를 도저히 모르겠어서 질문을 올렸는데, 결국 문제는 DFS에서 처음에 방문한 곳에 인접 노드가 하나도 없을 경우 while문을 빠져나가지 못하는 오류가 있었고 이를 수정하니 간단히 해결되었다.

 

내 코드:

import sys
from collections import deque
input = sys.stdin.readline

n,m,root = map(int,input().split())
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    i,j = map(int,input().split())
    nodes[i].append(j)
    nodes[j].append(i)

for i in range(len(nodes)):
    nodes[i].sort()

def dfs(start,n):
    visited = [False] * (n+1)
    stack = []
    answerli = []

    visited[start] = True
    answerli.append(start)
    stack.append(start)
    # 시작 노드에 인접 노드가 하나도 없을 경우
    if not nodes[start]:
        return [start]

    while stack:
        for idx,node in enumerate(nodes[stack[-1]]):
            if not visited[node]:
                # 방문 처리
                visited[node] = True
                answerli.append(node)
                stack.append(node)
                break
            # 주변 노드가 모두 방문되었다면
            if idx == len(nodes[stack[-1]]) - 1:
                stack.pop()
    
    return answerli

def bfs(start,n):
    visited = [False] * (n+1)
    queue = deque()
    answerli = []

    visited[start] = True
    answerli.append(start)
    queue.append(start)
    while queue:
        for node in nodes[queue.popleft()]:
            if not visited[node]:
                # 방문 처리
                visited[node] = True
                answerli.append(node)
                queue.append(node)

    return answerli



print(' '.join(map(str,dfs(root,n))))
print(' '.join(map(str,bfs(root,n))))

 

if문으로 그 특수한 경우만 걸러주면 된다.

 

1541번 : 잃어버린 괄호

 

문제를 이해하면 간단하게 풀 수 있는데, 의미없는 0을 제거하는 과정에서 약간 헤맸다.

 

내 코드:

f = input()
li = [char for char in f]

# 첫번째항 0 제거
while li[0] == '0':
    del li[0]

# 이후 항의 쓸모없는 0 제거
i = 1
while i < len(li):
    if li[i] == '0' and not li[i-1].isdigit():
        del li[i]
    else:
        i += 1

# 괄호 추가
i = 0
isOpen = False
while i < len(li):
    if li[i] == '-' and not isOpen:
        li.insert(i+1,'(')
        isOpen = True
    elif li[i] == '-' and isOpen:
        li.insert(i,')')
        isOpen = False

    i += 1

# 마지막에 괄호 닫지 않았을 시 닫기
if isOpen:
    li.append(')')

print(eval(''.join(li)))

 

이런 방법들을 사용해서 풀이했는데, 사실 이것보다 훨~씬 간단하게 풀 수 있다.

 

experien님의 코드:

e = [sum(map(int, x.split('+'))) for x in input().split('-')]
print(e[0]-sum(e[1:]))

 

캬~ 나도 이런 코드좀 써보고 싶다.. 뭔가 간단히 풀 수 있을꺼 같았는데, 장황하게 풀고 나서 숏코딩을 보면 그제야 깨닫게 된다...