미야's Day

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(graph, v, visited):
    global cnt
    visited[v] = cnt
    for i in sorted(graph[v]):
        if visited[i] == 0:
            cnt += 1
            dfs(graph, i, visited)

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
cnt = 1

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)



dfs(graph, r, visited)

for i in range(1, n + 1):
    print(visited[i])

1) 처음에 이 부분 추가 안해줘서 런타임에러

sys.setrecursionlimit(10 ** 6)

2) 다음엔 10 ** 6 을 10* 6이라고 쓰고 런타임에러

이걸 계속 발견하지 못하고 왜 에러나지 한참 고민함.. 분명 코드는 틀린게 없는데..)

하하.. 다 나임 ㅋ ㅋ .. (그래도 뭐.. 30분이면.. 한참은 아닌가 ) 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
     a, b = map(int, input().split())
     graph[a].append(b)
     graph[b].append(a)
visited = [0] * (n + 1)   #부모 노드를 담을 리스트

def dfs(root):
     for i in graph[root]:
          if visited[i] == 0:
               visited[i] = root
               dfs(i)
dfs(1)

for i in range(2, n + 1):
     print(visited[i])

from collections import deque

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

q = deque([(a, 1)])

while q:
    now, cnt = q.popleft()
    if now == b:
        print(cnt)
        break
    if now * 2 <= b:
        q.append((now * 2, cnt + 1))
    if now * 10 + 1 <= b:
        q.append((now * 10 + 1, cnt + 1))
else:
    print(-1)

이 문제는 구현으로 풀어도 되지만 bfs로 풀이를 해보았다.

구현으로 풀 시에는 top-down방식으로 b->a 로 풀어나가야 하지만, bfs풀이로는 bottom-up 방식으로 a -> b로 풀어가면 된다.

큐에 a값과 연산횟수값(처음1)을 넣어주고 시작한다.

popleft()로 큐의 값이 있을 때 빼주어 현재값을 now에, 연산횟수를 cnt에 저장한다.

now값과 b값을 비교하며 b값과 같으면 바로 연산횟수cnt를 출력하고 종료.

아니면, now값에 2를 곱한 값 또는 뒤에 1을 붙인 값(now * 10 + 1)이 b와 같거나 작을 때 큐에 넣어준다. (cnt값 + 1)

그렇게 now값이 b값과 같아질 때까지 반복해준다.

끝난 후 값이 같아지지 않는다면, -1을 출력한다. 

*내가 작성한 코드 

def solution(today, terms, privacies):
    answer = []
    today_year = int(today[:4])
    today_month = int(today[5:7])
    today_day = int(today[-2:])

    term_x = []
    for i in range(len(terms)):
        term_x.append(terms[i].split())

    privacie_x = []
    for i in range(len(privacies)):
        privacie_x.append(privacies[i].split())

    for index, i in enumerate(privacie_x):
        m = 0
        privacies_year = 0
        privacies_month = 0
        privacies_day = 0
        for j in term_x:
            if i[1] == j[0]:
                m = int(i[0][5:7]) + int(j[1])
                privacies_year = int(i[0][:4]) + (m // 12)
                privacies_month = m % 12
                privacies_day = int(i[0][-2:])
        if today_year == privacies_year and today_month == privacies_month and today_day == privacies_day:
            answer.append(index + 1)
        else:
            if today_year > privacies_year:
                answer.append(index + 1)
            elif today_year == privacies_year:
                if today_month > privacies_month:
                    answer.append(index + 1)
                elif today_month == privacies_month:
                    if today_day > privacies_day:
                        answer.append(index + 1)

    return answer
print(solution("2021.12.08", ["A 18"], ["2020.06.08 A"]))

결과 -> 1번, 17번 시간 초과

*정답 코드

def solution(players, callings):
  
    play_dict = dict()
    
    for index, name in enumerate(players):
        play_dict[name] = index
        
    for player in callings:
        idx = play_dict[player]
        front = players[idx - 1]
        
        play_dict[player] = idx - 1
        play_dict[front] = idx
        
        players[idx - 1] = player
        players[idx] = front
        
        
    return players

*깨달은 점: 시간 절약에는 dict() 를 활용하자! 딕셔너리 !!!!!!!

*bfs풀이

from collections import deque

def bfs(graph, start, visited):
    q = deque([start])
    visited[start] = True
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                q.append(i)

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
cnt = 0
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(1, n + 1):
    if not visited[i]:
        bfs(graph, i, visited)
        cnt += 1

print(cnt)

*dfs풀이

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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


n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
cnt = 0
visited = [False] * (n + 1)
for i in range(1, n+1):
    if not visited[i]:
        dfs(graph, i, visited)
        cnt += 1
print(cnt)

*DFS(깊이 우선 탐색)

#BFS(너비 우선 탐색)

백준 1260. [DFS와 BFS]문제 

*DFS: 인접한 노드 중 시작점 V부터 숫자가 작은 노드부터 방문하고, 이미 방문했다면 다시 돌아가 인접 노드를 찾는다.

*BFS:

1) 1번 노드 방문 후 큐에 삽입

2) 가장 앞에 있는 노드1을 pop 후, 인접 노드 2,3,4를 한꺼번에 q에 append

3) 가장 앞에 있는 노드2를 pop 후, 인접 노드 모두 방문처리 했으므로 append하지 않음 

4) 가장 앞에 있는 노드3를 pop 후, 인접 노드 모두 방문처리 했으므로 append하지 않음 

5) 가장 앞에 있는 노드4를 pop 후, 인접 노드 모두 방문처리 했으므로 append하지 않음 

6) q는 공백이 되고 종료. 

from collections import deque
#정점, 간선 수, 시작점 입력받음
n, m, v = map(int, input().split())

#초기값을 False로 만들어 그래프 선언
graph = [[False] * (n + 1) for _ in range(n+1)]

#연결된 정점 입력 후 그래프에 채워넣기
for i in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

#각각 dfs와 bfs 그래프의 방문 여부를 담을 리스트
visited1 = [False] * (n+1)
visited2 = [False] * (n+1)

#dfs알고리즘
def dfs(v):
    visited1[v] = True   #방문 처리
    print(v, end=" ")   #방문 후, 정점 출력
    for i in range(1, n+1):
        if not visited1[i] and graph[v][i] == 1:    #방문기록이 없고, v에 연결되어 있다면
            dfs(i)    #방문(재귀함수)
                      #호출될 때마다 visited는 1이되고 재귀되어 v에 i가 들어간다.

#bfs알고리즘
def bfs(v):
    q = deque([v])  #방문할 곳을 순서대로 넣을 큐 생성
    visited2[v] = True   #방문 처리
    while q:    #큐 안에 데이터가 없을 때까지 실행됨
        v = q.popleft()    #큐 맨 앞에 있는 값을 꺼내서 출력
        print(v, end=" ")
        for i in range(1, n+1):
            if not visited2[i] and graph[v][i] == 1:    #방문기록이 없고, v에 연결되어 있다면
                q.append(i)   #큐에 추가
                visited2[i] = True   #방문 처리

dfs(v)
print()
bfs(v)

<정리>

*DFS -> 스택과 재귀함수 사용

*BFS -> deque, while로 구현(시간복잡도가 낮은 popleft사용)

출처:https://kill-xxx.tistory.com/entry/Python-DFSBFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-1260-%EA%B7%B8%EB%A6%BC-%ED%92%80%EC%9D%B4

문제: 프로그래머스 PCCE기출문제 10번 데이터 분석

def solution(data, ext, val_ext, sort_by):
    answer = [[]]
    a = []
    sort = ["code", "date", "maximum", "remain"]
    for i in range(len(data)):
        for index, c in enumerate(sort):
            if ext == c:
                if data[i][index] < val_ext:
                    a.append(data[i])
    for num, s in enumerate(sort):
        if s == sort_by:
            answer = sorted(a, key=lambda x:x[num])


    return answer

sorted(a, key=lambda x:x[num]) 

-> 배열a에서 원소x의 x[num]번째 원소를 기준으로 오름차순 정렬한 결과를 반환한다. 

*처음 enumerate() 함수 쓰지 않고 푼 내 코드

def solution(board, moves):
    answer = 0
    bag = []
    for i in moves:
        for j in range(len(board)):
            if board[j][i-1] != 0:
                if bag and bag[-1] == board[j][i-1]:
                    del bag[-1]
                    answer += 2
                else:
                    bag.append(board[j][i-1])
                board[j][i-1] = 0
                break 

    return answer

* enumerate() 함수 사용한 코드

def solution(board, moves):
    answer = 0
    bag = []
    for i in moves:
        for index, j in enumerate(board):
            if j[i-1] != 0:
                if bag and bag[-1] == j[i-1]:
                    del bag[-1]
                    answer += 2
                else:
                    bag.append(j[i-1])
                board[index][i-1] = 0
                break 
    return answer