MINJU's code story

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

• 노드가 연결된 그래프, 방문배열, 결과값 저장할 장소를 만든다
• dfs에서 매개변수로 방문할 노드와 몇 번째 방문인지를 나타내는 cnt를 받는다
• 만약 방문 중인 노드와 타겟 노드와 같다면 현재 몇 번째 방문인지를 result에 append한다
• 그렇지 않을 경우 재귀로 dfs를 호출한다
• 만약 result 안에 아무것도 없으면 아무 관계도 아니므로 -1을 리턴하고 값이 있으면 result[0]의 값을 리턴한다.
• dfs를 재귀로 구현할 때 cnt를 어떻게 내보내야할지 고민이었는데, 이렇게 result라는 global 변수를 지정해두고 cnt를 result에 저장해주면 된다는 점을 배웠다

N = int(input())
x, y = map(int, input().split())
M = int(input())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
result = []

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

def dfs(v, cnt):
    if visited[v]:
        return
    
    cnt += 1
    visited[v] = True

    if v == y:
        result.append(cnt)

    for i in graph[v]:
        if not visited[i]:
            dfs(i, cnt)

dfs(x,0)

if len(result) == 0:
  print(-1)
else:
  print(result[0]-1)

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

• 3차원 배열이라서 어렵게 생각했는데 한 번에 값을 두 개 저장하는 대신 세 개 저장하는 큐를 만들면 됨.

import sys
from collections import deque

M, N, H = map(int, input().split())
graph = []
queue = deque([])

for i in range(H):
    temp = []
    for j in range(N):
        temp.append(list(map(int, sys.stdin.readline().split())))
        for k in range(M):
            if temp[j][k] == 1:
                queue.append([i, j, k]) #높이, 세로, 가로 (HNM)
    graph.append(temp)

dx = [-1,1,0,0,0,0]
dy = [0,0,1,-1,0,0]
dz = [0,0,0,0,1,-1]

while(queue):
    x, y, z = queue.popleft()

    for i in range(6):
        nx = x + dx[i]  #H 높이
        ny = y + dy[i]  #N 세로
        nz = z + dz[i]  #M 가로

        if 0<=nx<H and 0<=ny<N and 0<=nz<M and graph[nx][ny][nz] == 0:
            queue.append([nx,ny,nz])
            graph[nx][ny][nz] = graph[x][y][z] + 1


day = 0
for i in graph:
    for j in i:
        for k in j:
            if k==0:
                print(-1)
                exit(0)
        day = max(day,max(j))
print(day-1)

https://school.programmers.co.kr/learn/courses/30/lessons/92335

import math
def solution(n, k):
    answer = 0
    
    # 형변환
    new_n = ''
    while(n > 0):
        new_n = str(n%k) + new_n
        n = n//k
    
    # 0으로 구분짓고 공백과 1 제거
    nums = new_n.split('0')
    remove = ['', '1']
    nums = [int(i) for i in nums if i not in remove]
    
    # 소수 판별 코드
    def p_num(x):
        for i in range(2, int(math.sqrt(x)+1)):
            if x % i == 0:
                return False
        return True

    for i in nums:
        if p_num(i):
            answer += 1
    
    return answer

# n을 k진법으로 나타낸 문자열 반환
def conv(n, k):
    s = ''
    while n:
        s += str(n%k)
        n //= k
    return s[::-1]

# n이 소수인지 판정
def isprime(n):
    if n <= 1: return False
    i = 2
    while i*i <= n:
        if n%i == 0: return False
        i += 1
    return True

def solution(n, k):
    s = conv(n,k)
    cnt = 0
    for num in s.split('0'):
        if not num: continue # 빈 문자열에 대한 예외처리
        if isprime(int(num)): cnt += 1
    return cnt

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

• 연결리스트를 만든다
• 방문 배열을 만든다
• DFS를 구현해서 방문배열을 업데이트 시켜준다
• 방문배열에서 True인 갯수를 센다.
  • 나는 for문을 돌려서 셌는데 
  • 다른 코드 찾아보니 sum 함수 이용해서 하면 한 줄로 간단하게 풀 수 있더라

N = int(input())
M = int(input())

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

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

answer = -1

def dfs(x):
    if visited[x]:
        return
    
    visited[x] = True
    
    for i in graph[x]:
        if visited[i] != True:
            dfs(i)
dfs(1)

'''
for i in range(1,len(graph)):
    if visited[i] == True:
        answer += 1
print(answer)
'''

print(sum(visited)-1)

https://school.programmers.co.kr/learn/courses/30/lessons/134240?language=python3 

• 문자열 뒤집기 : 인덱싱을 뒤에서부터 해준다 -> [::-1]

def solution(food):
    answer = ''
    front = ''
    
    for i in range(1,len(food)):
        count = food[i] // 2
        front += str(i) * count
        
    back = front[::-1]
    answer = front + '0' + back
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/43165

• numbers 원소를 차례대로 앞선 index값에다가 더하거나 빼주면서 큐에 넣는다.
• 더하거나 뺀 값과 index도 튜플 형태로 함께 넣어준다.
• index 끝까지 다 큐에 넣으면 이제 차례대로 popleft하면서 target과 해당 값이 일치하는지 확인한다.

from collections import deque

def solution(numbers, target):
    answer = 0
    
    queue = deque()
    queue.append((numbers[0],0))
    queue.append((-numbers[0],0))
    
    while(queue):
        num, i = queue.popleft()
        i += 1
        if i < len(numbers):
            queue.append((num+numbers[i], i))
            queue.append((num-numbers[i], i))
        else:
            if num == target:
                answer += 1
    
    return answer

• numbers 원소의 양수 값과 음수 값을 튜플 형태로 리스트에 넣어준다.
• product 함수를 통해 cartisian product을 구하고 각 집합의 합을 구한다.
  • l 앞에 *을 붙여주는 이유는 리스트 안 원소를 하나씩 풀어줘야 해서.
  • *연산을 수행하면 리스트 내부의 값들이 가변인자로 변함.

• 합과 target값이 동일한 것의 갯수를 return한다.

from itertools import product

def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    
    return s.count(target)

• 지훈과 불의 이동경로를 추적할 큐와 방문배열을 각각 만들어줘야 한다. (큐 2개, 방문배열 2개)
• 지훈의 방문배열 체크할 때 같은 위치에 저장된 fire 시간이 0이 아니면서 현재 지훈 시간보다 작다면 이는 fire가 이미 번졌다는 의미이므로 지훈은 그곳에 갈 수 없다!! (핵심)
• 지훈의 큐를 꺼내다가 배열 크기를 초과하는 위치에 도달하게 된다면 이는 미로를 잘 빠져나간 것이므로 바로 지훈의 시간을 return해준다.
• 지훈의 큐를 다 꺼냈는데도 return값이 없다면 이는 지훈이 탈출하지 못했다는 의미이므로 bfs의 return값은 'IMPOSSIBLE'로 설정해준다.

import sys
from collections import deque
input = sys.stdin.readline
 
def bfs():
    # fire BFS
    while f_queue:    
        x, y = f_queue.popleft()
 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if nx < 0 or ny < 0 or nx >= R or ny >= C:
                continue
 
            if f_visited[nx][ny] != 0 or graph[nx][ny] == '#':
                continue
 
            f_visited[nx][ny] = f_visited[x][y] + 1
            f_queue.append((nx, ny))
 
    # jihoon BFS
    while j_queue:    
        x, y = j_queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if nx < 0 or ny < 0 or nx >= R or ny >= C:
                return j_visited[x][y]    # escape success
 
            # 방문 체크, 벽 체크
            # fire 방문 기록이 있으면서 기록된 값이 지훈의 현재 방문 기록보다 작다면 fire가 지훈 도착 전에 번졌다는 얘기이므로 
            # 해당 경로는 지훈이 지나갈 수 없다.
            if j_visited[nx][ny] != 0 or graph[nx][ny] == '#' or (f_visited[nx][ny] != 0 and f_visited[nx][ny] <= j_visited[x][y]+1):    # important code
                continue
 
            j_visited[nx][ny] = j_visited[x][y] + 1
            j_queue.append((nx, ny))
 
    return 'IMPOSSIBLE'    # j_queue가 끝날 때까지 탈출하지 못하면 escape fail
 
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
 
R, C = map(int, input().split())
graph = [list(input().strip()) for _ in range(R)]
f_queue, j_queue = deque(), deque()    
f_visited, j_visited = [[0] * C for _ in range(R)], [[0] * C for _ in range(R)]    
 
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'F':
            f_queue.append((i, j))
            f_visited[i][j] = 1
        elif graph[i][j] == 'J':
            j_queue.append((i, j))
            j_visited[i][j] = 1

print(bfs())

• 딕셔너리에서 없는 key값을 출력하려면 에러가 발생하므로 딕셔너리에 counter값 삽입 전  list = {'<': 0, '?': 0, '>': 0} 으로 초기화해준다. 
• 그리고 나서 list.update(s_list)를 통해 초기화한 딕셔너리를 counter로 계산한 값(s_list)으로 업데이트해준다. : 딕셔너리 update
• replace(대상 문자, 변경할 문자, 개수) : 맨 마지막에 개수를 명시해주면 앞에서부터 차례대로 문자열 변경해줌. 즉, for문 돌릴 필요 없음!!

from collections import Counter
# “<<??>>”  —>   “<<<>>>”

#s = '<<??>>'
#s = '>>>?>>'
s = '<<??<<?>'  #<<>><<>>
s_list = Counter(s)
s_list = dict(s_list.items())
list = {'<': 0, '?': 0, '>':0}
list.update(s_list)
print(list)   #{'<': 2, '?': 2, '>': 2}

open = 0
close = 0
if list['<'] > list['>']:
    close = list['<'] - list['>']
elif list['<'] < list['>']:
    open = list['>'] - list['<']
else:
    open = list['?'] // 2
    close = list['?'] - open

if open != 0:
    s = s.replace('?','<',open)

if close != 0:
    s = s.replace('?','>',close)

print(s)

바뀐 문자열을 출력하는 것이 아니라 닫힌 괄호가 최대가 되도록 필요한 괄호의 개수를 출력하는 것이라고 한다..