Coding 공부

import sys
input = sys.stdin.readline
def check(num):
    visited[num] = True
    stack = [num]

    while stack:
        node = stack.pop(0)

        for next_node in tree[node]:
            if tree[node][next_node] == 1:
                if not visited[next_node]:
                    visited[next_node] = True
                    stack.append(next_node)
                    tree[node][next_node] = 0
                    tree[next_node][node] = 0
                else:
                    return False
    return True
            


tc = 1
while True:
    N,M = map(int,input().split())
    if N+M == 0:
        break
    parent_cnt = [0]*(N+1)
    tree = [{} for _ in range(N+1)]
    for _ in range(M):
        x,y = map(int,input().split())
        tree[x][y] = 1
        tree[y][x] = 1
    cnt = 0
    visited = [False]*(N+1)
    for num in range(1,N+1):
        if not visited[num]:
            if check(num):
                cnt += 1
    if cnt == 0:
        print(f'Case {tc}: No trees.')
    elif cnt == 1:
        print(f'Case {tc}: There is one tree.')
    else:
        print(f'Case {tc}: A forest of {cnt} trees.')


    tc += 1

def check(cnt,total,di):
    global result
    if cnt == arr[0]:
        temp = 1
        for k in di:
            temp *= arr[dire.index(k)+1]/100
        result += temp
        return
    else:
        cu_x,cu_y = total[-1]
        for i in range(4):
            nx = cu_x + dx[i]
            ny = cu_y + dy[i]
            if (nx,ny) not in total:
                check(cnt+1,total+[(nx,ny)],di+[dire[i]])
    


# 동 서 남 북
dx = [0,0,1,-1]
dy = [1,-1,0,0]
dire = ['E','W','S','N']
arr = list(map(int,input().split()))
result = 0
check(0,[(0,0)],[])
print(ccnt)

def dfs(x,y,persent,cnt):
    global revers_persen,N,total
    if arr[x][y] == 1:
        revers_persen += persent
        return
    if cnt == N:
        return
    arr[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if persentlist[i]:
            dfs(nx,ny,persent*persentlist[i],cnt+1)
    arr[x][y] = 0



N,e,w,s,n = map(int,input().split())

e,w,s,n = e/100,w/100,s/100,n/100
dx = [0,0,1,-1]
dy = [1,-1,0,0]
persentlist = [e,w,s,n]
arr = [[0]*29 for _ in range(29)]

revers_persen = 0
dfs(14,14,1,0)
print(f'{1-revers_persen:.10f}')

import sys
sys.setrecursionlimit(10000)
def dfs(node):
    if not graph[node]:
        return 0
    ind = 0
    for next_node in graph[node]:
        distance_nodes[node][ind] += dfs(next_node) + graph[node][next_node]
        ind += 1
    return max(distance_nodes[node])
N = int(input())
graph = [{} for _ in range(N+1)]
parents = [0]*(N+1)
for _ in range(N-1):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    parents[A] += 1

distance_nodes = [[0]*(parents[ind]+2) for ind in range(N+1)]

dfs(1)
result = 0
for ind in range(1,N+1):
    distance_nodes[ind].sort(reverse=True)
    result = max(result,distance_nodes[ind][0]+distance_nodes[ind][1])
print(result)

첫 풀이방식은 다음과 같았다. 각 노드에서 가장 긴 노드들을 더해주는 방식이었다. 리프노드에 도착하면 0을 반환해주고 

재귀를 활용해서, 현재의 노드에서 자식노드까지의 거리 + 그 자식노드의 재귀함수를 통해 최대값을 더해주는 방식으로 했다.

이렇게 모든 노드들에 대해서 거리들을 전부 구한뒤, 모든 노드들의 거리의 합이 최대가 되는것을 구해주었다.

import sys
input = sys.stdin.readline
def dfs(ind):
    global N,result,max_Node
    visited = [True]*(N+1)
    stack = []
    stack.append((ind,0))
    visited[ind] = False
    while stack:
        node, distance = stack.pop()
        if distance > result:
            result = distance
            max_Node = node
        if graph[node]:
            for next_node in graph[node]:
                if visited[next_node]:
                    visited[node] = False
                    stack.append((next_node,distance+graph[node][next_node]))


N = int(input())
graph = [{} for _ in range(N+1)]
for _ in range(N-1):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C

result = 0
max_Node = 0

dfs(1)
dfs(max_Node)
print(result)

두번째 방식은 훨씬 간단하다. 두번의 dfs로 풀리는데 다음과 같다.

어느 한 지점에서 제일 거리가 멀리 떨어진 곳에 위치 한 곳을 구하면, 그 지점이 트리의 지점을 구할 수 있는 한 점인 것을 알 수 있다.

왜냐하면, 지름은 해당 트리에서 제일 긴 곳은 지름일테고, 그렇기 때문에 그 안에 있는 점의 가장 먼거리를 가지는 점은 지름의 두 점 중 하나가 될것이다.

이걸 이용해서 첫번째 dfs에서 트리의 지름에 해당하는 한 점을 구하고,

그 점에서 dfs를 통해 최대거리를 구하면 답이 된다.

def dfs(x,y):
    global N,M
    if x == N-1 and y == M-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] < arr[x][y]:
                    dp[x][y] += dfs(nx,ny)
        return dp[x][y]



import sys

input = sys.stdin.readline

N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*M for _ in range(N)]
print(dfs(0,0))

DP 와 DFS가 결합된 문제였다. 최소로 도달한거리를 DP에 저장해서 얻는것이었다. 마지막 우리가 도달해야하는 위치만 초기값을 1로 주고, 나머지는 전부 0으로 초기화한뒤 역으로 계싼해서 오는것이다.

from collections import deque


def dfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    stack = [V - 1]
    
    while stack:
        x = stack.pop()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N - 1, -1, -1):
            if graph[x][k] >= 1:
                graph[x][k] = 0
                graph[k][x] = 0
                stack.append(k)
    
    return result


def bfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    q = deque()
    q.append(V - 1)

    while q:
        x = q.popleft()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N):
            if graph[x][k] >= 1:
                graph[x][k] -= 1
                graph[k][x] -= 1
                
                q.append(k)
    
    return result



N, M, V = map(int, input().split())
arr = [list(map(int ,input().split())) for _ in range(M)]

dfs_res = dfs()
for i in range(len(dfs_res)):
    print(dfs_res[i], end=" ")
print()
bfs_res = bfs()
for i in range(len(bfs_res)):
    print(bfs_res[i], end=" ")
print()

DFS와 BFS 문제이다.

웹개발 중 코테 대비하면서 연습용으로 오랜만에 풀었던 문제라, 코드가 별로이다.

def solution(start,flag):
    global N
    stack = [start]
    visited = [True]*(N+1)
    ind = 0
    if flag:
        ind = -1
    result = []
    while stack:
        node_number = stack.pop(ind)
        if not visited[node_number]:
            continue
        visited[node_number] = False
        result.append(node_number)
        for next_node in sorted(graph[node_number],reverse=flag):
            if visited[next_node]:
                stack.append(next_node)
    return result




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)



print(*solution(V,True))
print(*solution(V,False))

 기본적인 풀이는 같다. DFS이냐, BFS이냐에 따라 트리거를 주었고, DFS일때는 pop하는 index를 -1로 아니면 0으로 주었다.

그리고 dfs는 뒤에서부터 pop이 되므로, graph를 내림차순으로 정렬해주고, bfs는 오름차순으로 정렬해주는것만 다르다.

def dfs(i,cnt):
    global result
    visited[i] = False
    if cnt >= 5:
        result = True
        return
    for ind in graph[i]:
        if visited[ind]:
            dfs(ind,cnt+1)
    visited[i] = True


N,M = map(int,input().split())
graph = [[] for _ in range(N)]


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

visited = [True]*N
result = False
for i in range(N):
    dfs(i,1)
    if result:
        break
print(int(result))

DFS를 해서 깊이가 4 이상이면 True를 반환해주면 되는 문제이다.

위와 같이 재귀를 해서 풀어도 되고, 

import sys
input = sys.stdin.readline
def solution():
    global N
    for dep0 in range(N):
        for dep1 in graph[dep0]:
            for dep2 in graph[dep1]:
                if dep0 == dep2:
                    continue
                for dep3 in graph[dep2]:
                    if dep3 == dep1 or dep3 == dep0:
                        continue
                    for dep4 in graph[dep3]:
                        if dep4 != dep0 and dep4 != dep1 and dep4 != dep2:
                            return 1
    return 0

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

print(solution())

깊이가 그리 깊지 않으니 하드코딩으로 분기처리를 해주어도 풀 수 있다.

from collections import deque

def bfs(x,y,color):
    global N
    stack = deque()
    stack.append((x,y))
    if color == 'B':
        chk = 2
    else:
        chk = 3
    visited[x][y] = chk
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if not visited[nx][ny] and arr[nx][ny] == color:
                    visited[nx][ny] = chk
                    stack.append((nx,ny))
    
def new_bfs(x,y,chk):
    global N
    stack = deque()
    stack.append((x,y))
    visited[x][y] = 0
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <=nx<N and 0<=ny<N:
                if visited[nx][ny] == chk:
                    visited[nx][ny] = 0
                    stack.append((nx,ny))

N = int(input())


arr = [list(input()) for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited = [[0]*N for _ in range(N)]
cnt_a = 0
cnt_b = 0
for x in range(N):
    for y in range(N):
        if not visited[x][y]:
            bfs(x,y,arr[x][y])
            cnt_a += 1

for x in range(N):
    for y in range(N):
        if visited[x][y]:
            new_bfs(x,y,visited[x][y])
            cnt_b += 1

print(cnt_a,cnt_b)

2개의 BFS로 나누어, 3개의 색으로 구분할때와 2가지 색으로 구분할때 나눠서 탐색해주면 된다.

여기서 별다른 건 없고, visited 라는 리스트를 두번 만드는게 싫어서, 첫번째 bfs에서 visited에 체크하는 숫자를 청색 vs 녹색,빨간색을 서로 다르게 해주었고,

두번째 bfs에서는 원본 배열이 아닌 visited 함수를 통해 bfs를 돌려주었다.

# 16946 벽 부수고 이동하기 4

# dfs를 해준다. 여기서 일반적인 dfs와 다른점은 방문표시 대신 해당 위치의 값을 들어온 index값으로 변형시켜준다.
def dfs(x,y,index):
    global index_dict,N,M

    stack = [(x,y)]
    cnt = 1
    arr[x][y] = index
    while stack:
        cx,cy = stack.pop()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if not arr[nx][ny]:
                    stack.append((nx,ny))
                    arr[nx][ny] = index
                    cnt += 1
    # dfs를 전부 한뒤에 그 개수를 딕셔너리에 저장해준다.
    index_dict[index] = cnt




# dfs를 이용해서 쉽게 풀수 있었던 문제


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

dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,list(input()))) for _ in range(N)]
# 원본이 저장된 arr
result = [['0']*M for _ in range(N)]
# 결과값들을 저장해놓는 result 배열을 만들어둔다.

# 빈칸인 개수를 세주기 위해서 초기값을 -1로 해줬다. 왜냐하면 arr에는 1,0이 있으므로 겹쳐지지 않게 -1부터 시작해서 1씩 작아지게 해줬다.
# 그리고 해당 인덱스에 연결된 개수를 저장하기 위한 index_dict라는 딕셔너리를 미리 만들어줬다.
index = -1
index_dict = {}

# 빈칸의 개수를 세어주기 위한 dfs 공정
for x in range(N):
    for y in range(M):
        if not arr[x][y]:
            dfs(x,y,index)
            index -= 1

for x in range(N):
    for y in range(M):
        if arr[x][y] == 1:
            # 원본 배열에서 벽이 있을때, 그 벽 주변의 상황을 파악하고, 그 중에 1이 아닌 우리가 설정한 index값을 집합에 저장해준다.
            temp = set()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] != 1:
                        temp.add(arr[nx][ny])
            # 기본값은 1이고, temp에 저장된 index들을 반복문을 돌려 움직일수 있는 칸의 개수를 세준다.
            move_wall = 1
            for index in temp:
                move_wall += index_dict[index]
            # 그리고 result에 10으로 나눈 나머지를 string형태로 저장해준다.
            result[x][y] = str(move_wall%10)
# join을 이용해 출력해준다.
for row in result:
    print(''.join(row))

 이 문제는 union find 문제와 비슷하게 빈 위치의 그룹을 지어주면 된다.

최종 결과가 나올 result라는 2차원 배열을 '0'으로 초기화 해줬다. 왜냐하면, 나중에 출력을 할때, join을 쓰기 위해, 문자열 형태로 초기화 해줬다.

먼저 주어진 행렬의 빈칸들의 그룹의 정보를 저장해줄 index_dict을 만들어줬다. 여기서 key는 index 을 기준으로 해줬고, value는 그 그룹의 개수이다.

여기서 index 초기값을 -1을 해준 이유는 문제에서 0,1을 이미 쓰고 있어서, 겹치지 않기 위해 음수로 해줬다.

그러면 주어진 행렬에서 dfs 아니면 bfs를 해주면서, 빈칸들의 그룹들을 나눠 주는 작업을 해주고, 그 그룹의 크기와 index를 index_dict에 저장을 해주면서, 원본행렬에도 index를 대신 넣어준다.

벽 부수고 이동하기를 해주는 방법은 원본 행렬에서 1인 곳을 찾아서, 상하좌우에 있는 1이 아닌 값들을 집합에 저장을 해준다. 그리고 집합에 저장된 index들을 꺼내 전체 index_dict에 저장된 값들을 더해주면 된다. 그리고 원래 있던 벽이 무너지는 거니 1이 기본값이다.

그리고 결과값을 10으로 나눈 나머지를 문자열 형태로 저장해줬다.