Coding 공부

import sys



input =sys.stdin.readline

def wall_move(origin_list):
    temp = []

    for x,y in origin_list:
        if x == 7:
            continue
        else:
            arr[x][y] = '.'
            temp.append((x+1,y))
    for x,y in temp:
        arr[x][y] = '#'
    return temp



arr = []
wall = []
for x in range(8):
    input_list = list(input().strip())
    for y in range(8):
        if input_list[y] == '#':
            wall.append((x,y))
    arr.append(input_list)

start = (7,0)

stack = []
stack.append(start)
result = 0
times = 0
dx = [-1,0,1,-1,0,1,-1,0,1]
dy = [-1,-1,-1,0,0,0,1,1,1]
while stack:
    visited = [[True]* 8 for _ in range(8)]
    new_stack = []

    for x,y in stack:
        if arr[x][y] == '#':
            continue
        for i in range(9):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<8 and 0<=ny<8 and arr[nx][ny] == '.' and visited[nx][ny]:
                new_stack.append((nx,ny))
                visited[nx][ny] = False
    
    if (0,7) in new_stack:
        result = 1
        break


    wall = wall_move(wall)

    stack = new_stack[:]

print(result)

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

import sys
import heapq
input = sys.stdin.readline


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

dp = [-1]*100001
stack = []
dp[N] = 0
root_dict = {}
root_dict[N] = -1
heapq.heappush(stack,(0,N))
if N == M:
    print(0)
    print(N)
else:
    flag = False
    while stack:
        cnt, x = heapq.heappop(stack)
        for ind,nx in enumerate([2*x,x-1,x+1]):
            if 0<=nx<100001:
                if dp[nx] == -1:
                    dp[nx] = cnt + 1
                    root_dict[nx] = x
                    heapq.heappush(stack,(cnt+1,nx))
                    if nx == M:
                        find_route = [nx]
                        cu_route = nx
                        while cu_route != N:
                            cu_route = root_dict[cu_route]
                            find_route.append(cu_route)
                        flag = True
                        print(cnt+1)
                        print(*reversed(find_route))
                        break
        if flag:
            break

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


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

dp = [-1]*100001
stack = deque()
dp[N] = 0
root_list = [-1]*100001
stack.append((0,N))
if N > M:
    print(N-M)
    print(' '.join(map(str,range(N,M-1,-1))))
elif N == M:
    print(0)
    print(N)
else:
    flag = False
    while stack:
        cnt, x = stack.popleft()
        for ind,nx in enumerate([2*x,x-1,x+1]):
            if 0<=nx<100001:
                if dp[nx] == -1:
                    dp[nx] = cnt + 1
                    root_list[nx] = x
                    stack.append((cnt+1,nx))
                    if nx == M:
                        find_route = [nx]
                        cu_route = nx
                        while cu_route != N:
                            cu_route = root_list[cu_route]
                            find_route.append(cu_route)
                        flag = True
                        print(cnt+1)
                        print(*reversed(find_route))
                        break
        if flag:
            break

from collections import deque

def roll(direction,red,blue):
    global arr,visited
    stack = deque()
    red = [*red,True]
    blue = [*blue,True]
    stack.append((red,blue))
    while stack:
        r,b = stack.popleft()

        r_x,r_y,r_state = r
        b_x,b_y,b_state = b
        visited[r_x][r_y] = False
        if r_state:
            nr_x = r_x + dx[direction]
            nr_y = r_y + dy[direction]
            if 0<=nr_x<N and 0<=nr_y<M:
                if nr_x == b_x and nr_y == b_y:
                    if not b_state:
                        r_state = False
                else:
                    if arr[nr_x][nr_y] == '#':
                        r_state = False
                    elif arr[nr_x][nr_y] == 'O':
                        r_state = False
                        r_x = -1
                        r_y = -1
                    else:
                        r_x = nr_x
                        r_y = nr_y
        if b_state:
            nb_x = b_x + dx[direction]
            nb_y = b_y + dy[direction]
            if 0<=nb_x<N and 0<=nb_y<M:
                if nb_x == r_x and nb_y == r_y:
                    if not r_state:
                        b_state = False
                else:
                    if arr[nb_x][nb_y] == '#':
                        b_state = False
                    elif arr[nb_x][nb_y] == 'O':
                        b_state = False
                        b_x = -1
                        b_y = -1
                    else:
                        b_x = nb_x
                        b_y = nb_y
        
        if not r_state and not b_state:
            if b_x == -1:
                return -1
            if r_x == -1:
                return 1
            return [r_x,r_y,b_x,b_y]
        
        stack.append(([r_x,r_y,r_state],[b_x,b_y,b_state]))


def bfs(r,b,g):
    global arr
    stack = deque()
    stack.append((r,b,0))
    visited[r[0]][r[1]] = False
    while stack:
        red,blue,cnt = stack.popleft()
        if cnt >= 10:
            return -1
        for i in range(4):
            nx = red[0] + dx[i]
            ny = red[1] + dy[i]
            if 0<=nx<N and 0<=ny<M:
                result = roll(i,red,blue)
                if type(result) == int:
                    if result == 1:
                        return cnt+1
                else:
                    nr = [result[0],result[1]]
                    nb = [result[2],result[3]]
                    stack.append((nr,nb,cnt+1))
    return -1
dx = [-1,1,0,0]
dy = [0,0,-1,1]


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

arr = []
red_ball = []
blue_ball = []
goal = []
visited = [[True]*M for _ in range(N)]
for x in range(N):
    temp = list(input())

    for y in range(M):
        if temp[y] == 'R':
            temp[y] = '.'
            red_ball = [x,y]
        elif temp[y] == 'B':
            temp[y] = '.'
            blue_ball = [x,y]
        elif temp[y] == 'O':
            goal = [x,y]
    arr.append(temp)
print(bfs(red_ball,blue_ball,goal))

import sys

input = sys.stdin.readline

T = int(input())

def find_parents(node):
    parent_list = [node]

    while parent_num[node] != -1:
        parent = parent_num[node]
        parent_list.append(parent)
        node = parent

    return parent_list



for _ in range(T):
    N = int(input())
    parent_num = [-1]*(N+1) # 해당 index의 부모가 안에 들어가 있다.
    for _ in range(N-1):
        parent,child = map(int,input().split())
        parent_num[child] = parent


    num1,num2 = map(int,input().split())

    parents1 = find_parents(num1)
    parents2 = find_parents(num2)

    if len(parents1) < len(parents2):
        parents1,parents2 = parents2, parents1
    result = -1
    for num in parents1:
        if num in parents2:
            result = num
            break
    print(result)

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}')

def belman_ford(S,E):
    INF = float('inf')
    earn_list = [INF]*N
    earn_list[S] = -benefit[S]
    for _ in range(M):
        for node in range(N):
            for next_node in bus_pay[node]:
                next_pay = bus_pay[node][next_node]
                if earn_list[next_node] > earn_list[node] + next_pay - benefit[next_node]:
                    earn_list[next_node] = earn_list[node] + next_pay - benefit[next_node]

    cycle_node = set()
    for _ in range(M):
        for node in range(N):
            for next_node in bus_pay[node]:
                next_pay = bus_pay[node][next_node]
                if earn_list[next_node] > earn_list[node] + next_pay - benefit[next_node]:
                    earn_list[next_node] = earn_list[node] + next_pay - benefit[next_node]
                    cycle_node.add(next_node)
                    cycle_node.add(node)
    if earn_list[E] == INF:
        print('gg')
    else:
        if len(cycle_node)>0:
            visted = [False]*N
            path_list = list(cycle_node)
            while path_list:
                node = path_list.pop(0)
                for next_node in bus_pay[node]:
                    if visted[next_node] == False:
                        visted[next_node] = True
                        path_list.append(next_node)
            if visted[E]:
                print('Gee')
                return
            else:
                print(-earn_list[E])
        else:
            print(-earn_list[E])



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


bus_pay = [{} for _ in range(N)]
for _ in range(M):
    a_city,b_city,pay = map(int,input().split())
    bus_pay[a_city][b_city] = min(bus_pay[a_city].get(b_city,float('inf')),pay)

benefit = list(map(int,input().split()))



belman_ford(start_city,end_city)

import sys

sys.setrecursionlimit(1000)
def dfs(node,cnt):
    for next_node,val in enumerate(arr[node]):
        if val and visited[next_node] == 0:
            visited[next_node] = cnt
            dfs(next_node,cnt)





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

tour_list = list(map(int,input().split()))

visited = [0]*N
cnt = 1
for i in range(N):
    if visited[i] == 0:
        visited[i] = cnt
        dfs(i,cnt)
        cnt += 1

result = 'YES'
init = visited[tour_list[0]-1]
for city in tour_list[1:]:
    if visited[city -1] != init:
        result = 'NO'
print(result)

첫 풀이 방식은 다음과 같았다.

DFS를 통해 모두 연결이 된대를 같은 cnt로 표시를 했다. 그런데 만약에 같은 cnt가 아니라면 tour_list에서 한번에 갈수 없는 곳 이므로 result를 No로 출력했다.

import sys
input = sys.stdin.readline

def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
    if x > y:
        x,y = y,x
    make_set[y] = x
    for i in range(N+1):
        if make_set[i] != i:
            make_set[i] = find_parent(make_set[i])

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
     
    return find_parent(make_set[ind])
N = int(input())
M = int(input())
edges = []
for i in range(N):
    graph_list = list(map(int,input().split()))
    for j in range(N):
        if graph_list[j] == 1:
            edges.append((i+1,j+1))

tour_list = list(map(int,input().split()))
make_set = [i for i in range(N+1)]

for edge in edges:
    node_a,node_b = edge
    if find_parent(node_a) != find_parent(node_b):
        union(node_a,node_b)

init_value = make_set[tour_list[0]]
result = 'YES'
for city in tour_list:
    if init_value != make_set[city]:
        result = 'NO'
        break
print(result)

좀 더 원론적인 union find를 해서 같은 집합인지 아닌지 판별을 했다.

그리고 난뒤에 같은 집합이 아니면 No를 출력하게 했다.