[백준] 1260, 1436 - Python3

shsh·2021년 9월 27일

목록 보기

5/45

1436. 영화감독 숌

https://www.acmicpc.net/problem/1436

내 풀이 - 실패

N = int(input())

end = "666"

print(int(str(N-1)+end))

666, 1666, 2666, 3666, ... 의 순서라면
(N-1) 666 의 형태를 갖는다고 생각함

근데.. 아니었다...
5666 다음에는 6666 이 아니라 6660 이 됨
=> ..., 5666, 6660, 6661, 6662, 6663, 6664, ...

다른 사람의 풀이

n = int(input())
x = 666

while n:
    if '666' in str(x):
        n -= 1
    x += 1

print(x - 1)

666 부터 시작해서 666 이 포함된 숫자일 때만 시리즈 제목으로 사용 => n - 1
나머지는 666 이 포함될 때까지 1 씩 증가

허무하다...

1260. DFS와 BFS

https://www.acmicpc.net/problem/1260

내 풀이 - 실패

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

graph = {i:[] for i in range(1, N+1)}

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for g in graph.keys():
    graph[g].sort()

b = []
d = []

### DFS
visited = {i:0 for i in range(1, N+1)}
def dfs(graph, v):
    visited[v] = 1
    d.append(v)

    for i in graph[v]:
        if visited[i] == 0:
            dfs(graph, i)
    
dfs(graph, V)
print(d)

### BFS
visited = {i:0 for i in range(1, N+1)}
queue = [V]
while queue:
    q = queue.pop(0)
    visited[q] = 1
    b.append(q)
    for i in graph[q]:
        if visited[i] == 0:
            visited[i] = 1
            queue.append(i)

print(b)

graph 를 만들어서 각 정점마다 연결된 노드들을 저장
작은 숫자부터 가야한다고 했으므로 sort()

dfs 는 visited 와 재귀 함수를 이용해서 탐색
bfs 는 visited 와 queue 를 이용해서 탐색

한 11퍼 통과하다 실패했다...

참고) 1 ~ N 까지의 숫자이므로 굳이 딕셔너리 사용할 필요 X -> 리스트 사용

내 풀이 2 - 성공

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

graph = {i:[] for i in range(1, N+1)}

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for g in graph.keys():
    graph[g].sort()

b = []
d = []

### DFS
visited = {i:0 for i in range(1, N+1)}
def dfs(graph, v):
    print(v, end=' ')
    visited[v] = 1

    for i in graph[v]:
        if visited[i] == 0:
            dfs(graph, i)
    
dfs(graph, V)
print()

### BFS
visited = {i:0 for i in range(1, N+1)}
queue = [V]
while queue:
    q = queue.pop(0)
    visited[q] = 1
    print(q, end= ' ')
    for i in graph[q]:
        if visited[i] == 0:
            visited[i] = 1
            queue.append(i)

dfs, bfs 모두 탐색하는 과정에서
결과값을 변수에 저장하지 않고 바로 print 를 해주니까 통과 됐다

print(q, end= ' ') => 다음 값이 공백을 사이에 두고 같은 줄에 출력 (엔터 X)