Coding 공부

# 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으로 나눈 나머지를 문자열 형태로 저장해줬다.

# # # 9466 텀 프로젝트
import sys
sys.setrecursionlimit(100000)
 
 
 
def dfs(node):
    global result
    visited[node] = False
    total.append(node)
    next_node = graph[node]
    if not visited[next_node]:
        if next_node in total:
            find_index = total.index(next_node)
    
            result +=total[find_index:]
        return
    else:
        dfs(next_node)
 
 
for _ in range(int(input())):
    N = int(input())
    graph = [0]+list(map(int,sys.stdin.readline().split()))
    visited = [True] *(N+1)
    result = []
    for ind in range(1,N+1):
        if visited[ind]:
            total = []
            dfs(ind)
    print(N-len(result))

문제를 풀때, 어떻게 풀어야할지 고민을 했던 문제이다. 문제를 읽어보면, 사이클을 이루는 경우에만, 팀이 될수 있다는 것을 알 수 있다. 

그래서 DFS 재귀를 통해서, 내가 방문한 곳을 다시 방문하게 된다면, 사이클을 이루게 되는 것이기 때문에, 결과값에 추가해주었다. 중간의 find_index 같은 경우 사이클을 이루어지는 최초지점을 찾아서 저장해주기 위함이다.

만약 1,2,3,4,5 가 있고, 각각 2,3,4,5,2를 선택했다고 하면 dfs를 했을때 total에는 [1,2,3,4,5]가 저장되어있을 것이다. 하지만, 1은 문제에 주어진 조건을 만족하지 못하고, 팀이 되지 못한다. 그래서 사이클이 최초로 시작되는 2를 기준으로 잘라주기 위함이다.

for _ in range(int(input())):
    N = int(input())
    graph = list(map(int,input().split()))
    visited = [0]*N
    cnt = 0
    for current_node in range(N):
        if not visited[current_node]:
            next_node = current_node
            while visited[next_node] == 0:
                visited[next_node] = 1
                next_node = graph[next_node] - 1
            cycle_index = current_node
            while cycle_index != next_node:
                cnt += 1
                cycle_index = graph[cycle_index] - 1
 
    print(cnt)
 

좀 더 깔끔한 풀이다. 위와 비슷하지만, 최초로 사이클이 시작되는 노드는 중간의 while문을 통과하고 나온 next_node일것이다.

그러면 처음 노드인 current_node를 복사해, cycle_index라고 하고, 이 cycle_index가 next_node와 같지 못하면, 사이클에 포함되지 않는 노드임을 알 수 있다. 이 next_node는 사이클이 최초로 발생하는 노드의 위치이기 때문에, 만약 current_node에서 사이클이 시작됬다면 cycle_node와 next_node는 동일할 것이다. 

그래서, 이 cycle_node를 똑같이 반복문을 돌리면서 next_node와 같아질때까지 반복을 한다. 그게 곧 팀에 포함되지 않는 사람의 수를 나타내는 것임을 알 수 있다.

# 15591 MooTube
 
N,Q = map(int,input().split())
 
graph = {i:[] for i in range(N+1)}
 
for _ in range(N-1):
    A,B,USADO = map(int,input().split())
    graph[A].append((B,USADO))
    graph[B].append((A,USADO))
 
 
for _ in range(Q):
    K,start = map(int,input().split())
    visited = [True]*(N+1)
    visited[start] = False
    stack = [(start,float('inf'))]
    result = 0
    while stack:
        node,usado = stack.pop()
 
        for next_node,next_usado in graph[node]:
            next_usado = min(usado,next_usado)
            if next_usado >= K and visited[next_node]:
                result += 1
                stack.append((next_node,next_usado))
                visited[next_node] = False
    print(result)

그래프을 활용한 문제이다. 여기서는 주어진 node를 기준으로 연결이 되어있는 것을 전부 확인하면서, 최소 USADO를 갱신해주면 된다. 그래서 만약에 중간에 주어진 K보다 USADO가 나올시에는 멈추도록해주고, 그외에 방문하지 않은 노드이고, K보다 큰 usado일때에는 stack에 넣어서 계속 check를 해주었다.

# 11403 경로 찾기
 
 
 
N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
for k in range(N):
    for x in range(N):
        for y in range(N):
            if arr[x][k] + arr[k][y] == 2:
                arr[x][y] = 1
 
for i in range(N):
    print(*arr[i])

풀고보니 플로이드 와샬 문제였다.

중간 경로를 통해서 두개가 연결이 되는 경우 arr를 갱신해주는 방식으로 했다.

이 방식 말고도 BFS,DFS를 통해 node들을 탐색해서 푸는 방식도 있다.

# 18231 파괴된 도시
 
 
 
 
 
 
N,M = map(int,input().split())
 
graph = {i:[] for i in range(N+1)}
 
for _ in range(M):
    node1,node2 = map(int,input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)
 
destory_cnt = int(input())
destroy_citys = list(map(int,input().split()))
result = []
destroyed = []
for destroy_city in destroy_citys:
    temp = [destroy_city]
    for city in graph[destroy_city]:
        if city not in destroy_citys:
            break
        else:
            temp.append(city)
    else:
        result.append(destroy_city)
        destroyed.extend(temp)
    if len(set(destroyed)) == destory_cnt:
        print(len(result))
        result.sort()
        print(' '.join(list(map(str,result))))
        break
else:
    print(-1)

이 문제는 여러가지 경우의 답이 나올수 있으나, 정답이 되는 1개만 출력하면 된다.

기본 원리는 이렇다. 그래프라는 딕셔너리에 양방향으로 노드를 전부 저장해놓는다.

그리고 파괴된 도시 목록을 입력을 받아, for문을 돌리는데, 만약 파괴된 도시 중 하나의 인접 노드들 중에 파괴된 노드들이 하나도 없으면 for문을 중지하고, 나온다. 그렇지 않을경우는 해당 도시는 파괴가 시작된 도시로 볼 수 있으므로, 결과목록에 넣어준다.

또한 해당 도시로 폭파된 도시 목록도 별도의 리스트에 저장해준다.

이렇게 반복을 해주면서, 별도로 저장해놓은 폭파된 도시목록을 set을 해줬을때의 길이가, 전체 파괴된 도시수와 동일하다면 for문을 중지하고, 결과를 보여준다.

위의 해당사항이 하나도 없을 시에는 -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}')

이 방법은 역으로 되지 않는 경우의 확률을 구해서, 1에서 빼주는 것이다. 이때는, format을 통해 소숫점 자리수까지 나오게 해줘야한다.

import itertools
import collections
 
def bfs(arr,team):
    q=collections.deque()
    q.append(arr)
    cnt=1
    visited[arr]=True
    while q:
        node=q.popleft()
        for k in graph[node]:
            if visited[k]==False and k in team:
                visited[k]=True
                q.append(k)
                cnt+=1
    if cnt==len(team):
        return True
    else:
        return False
 
 
N=int(input())
arr=list(range(1,N+1))
people=[0]
 
people.extend(list(map(int,input().split())))
graph=[[]]
people_total=sum(people)
for i in range(N):
    temp=list(map(int,input().split()))
    graph.append(temp[1:])
min_number=999999999999999
for i in range(1,N//2+1):
    b=itertools.combinations(arr,i)
    for k in b:
        a_team=list(k)
        b_team=list(set(arr)-set(k))
        
        visited=[False]*(N+1)
        
        if bfs(a_team[0],a_team) and bfs(b_team[0],b_team):        
            a_team_sum=0
            for tt in a_team:
                a_team_sum+=people[tt]
            b_team_sum=people_total-a_team_sum
            if abs(b_team_sum-a_team_sum)<=min_number:
                min_number=abs(b_team_sum-a_team_sum)       
    if min_number==0:
        break
if min_number>1000:
    print(-1)
else:
    print(min_number)

기본적인 그래프 이론이다.

기본 컨셉은 combination을 이용해 전체 N에서 절반만큼만 구한다. 이유는 조합은 n-k 와 k일떄의 조합은 같기 때문이다.

그렇게 구한 조합에서 set을 이용해서 서로 뺄샘으로 a_team과 b_team을 구하고, 경로탐색을 통해 서로 이어진 숫자와 팀의 길이와 같은지 구분을 하고, 게리멘더링이 성립되는경우에 두 팀간의 격차를 구하고, 최소값을 갱신해준다.