Coding 공부

import sys
from collections import deque
def input():
    return sys.stdin.readline()
N,M = map(int,input().split())
 
sams = list(map(int,input().split()))
 
visited_set = set(sams)
 
queue = deque()
for sam in sams:
    queue.append((sam,0))
 
cnt = 0
result = 0
while queue:
    cur_node,dis = queue.popleft()
    result += dis
    cnt += 1
    if cnt == N+M:
        break
    for next_node in [cur_node+1,cur_node-1]:
        if next_node not in visited_set:
            visited_set.add(next_node)
            queue.append((next_node,dis+1))
print(result)

이 문제는 샘터를 기준으로 bfs를 하면서, 방문 표시를 해주면 되는 문제였다.

종료조건은 샘터의 개수와 집의 개수를 합친 개수가 되면 종료가 되게 하면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
def fishing(y):
    for x in sorted(shark_dict[y].keys()):
        if shark_dict[y][x]:
            temp = shark_dict[y][x][2]
            del shark_dict[y][x]
            return temp
    return 0
R,C,M = map(int,input().split())
 
shark_dict = [{} for _ in range(C)]
for _ in range(M):
    x,y,speed,dire,size = map(int,input().split())
    x -= 1
    y -= 1
    dire -= 1
    shark_dict[y][x] = [dire,speed,size]
 
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
    remain_cnt = 0
    move_shark_dict = [{} for _ in range(C)]
    result += fishing(y)
    for shark_y in range(C):
        for shark_x in shark_dict[shark_y]:
            dire, speed, size = shark_dict[shark_y][shark_x]
            nx = shark_x
            ny = shark_y
            if dire in [0,1]:
                for _ in range(speed):
                    nx += dx[dire]
                    if nx >= R-1 or nx <= 0:
                        dire = reverse[dire]
                        if nx >= R:
                            nx = R - 2
                        elif nx<0:
                            nx = 1
 
            else:
                for _ in range(speed):
                    ny += dy[dire]
                    if ny >= C-1 or ny <= 0:
                        dire = reverse[dire]
                        if ny >=C:
                            ny = C-2
                        elif ny<0:
                            ny = 1
            if move_shark_dict[ny].get(nx):
                if move_shark_dict[ny][nx][2] < size:
                    move_shark_dict[ny][nx] = [dire, speed, size]
            else:
                move_shark_dict[ny][nx] = [dire,speed,size]
                remain_cnt += 1
    if remain_cnt:
        shark_dict = [{} for _ in range(C)]
 
        for y in range(C):
            for x in move_shark_dict[y]:
                shark_dict[y][x] = move_shark_dict[y][x]
    else:
        break
 
print(result)

문제에서 정해준대로 구현과 시뮬레이션을 정직하게 한 방법이다.

즉 이동도 한칸 한칸씩 이동을 해서 통과는 했지만 시간은 오래 걸리는 풀이 방법이다.

import sys
def input():
    return sys.stdin.readline().rstrip()
 
def fishing(y):
    for x in sorted(shark_dict[y].keys()):
        if shark_dict[y][x]:
            temp = shark_dict[y][x][2]
            del shark_dict[y][x]
            return temp
    return 0
R,C,M = map(int,input().split())
 
shark_dict = [{} for _ in range(C)]
for _ in range(M):
    x,y,speed,dire,size = map(int,input().split())
    x -= 1
    y -= 1
    dire -= 1
    shark_dict[y][x] = [dire,speed,size]
 
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
    remain_cnt = 0
    move_shark_dict = [{} for _ in range(C)]
    result += fishing(y)
 
    for shark_y in range(C):
        for shark_x in shark_dict[shark_y]:
            dire, speed, size = shark_dict[shark_y][shark_x]
            nx = shark_x + dx[dire]*speed
            ny = shark_y + dy[dire]*speed
            if dire in [0,1]:
                while not(0<=nx<R):
                    if nx<0:
                        nx = -nx
                        dire = reverse[dire]
                    else:
                        nx = (R-1)-(nx-(R-1))
                        dire = reverse[dire]
            else:
                while not(0<=ny<C):
                    if ny<0:
                        ny = -ny
                        dire = reverse[dire]
                    else:
                        ny = (C-1)-(ny-(C-1))
                        dire = reverse[dire]
 
            if move_shark_dict[ny].get(nx):
                if move_shark_dict[ny][nx][2] < size:
                    move_shark_dict[ny][nx] = [dire, speed, size]
            else:
                move_shark_dict[ny][nx] = [dire,speed,size]
                remain_cnt += 1
    if remain_cnt:
        shark_dict = [{} for _ in range(C)]
 
        for y in range(C):
            for x in move_shark_dict[y]:
                shark_dict[y][x] = move_shark_dict[y][x]
    else:
        break
 
print(result)

두번째 풀이는 방향을 한번에 구하는 것을 통해 시간을 아낄수 있었다. 정확히 말하면 한번은 아니지만, 한칸한칸씩 움직이는 것보다 빠르게 만들었다.

import sys
def input():
    return sys.stdin.readline().rstrip()
 
def fishing(y):
    for x in range(R):
        if pos[x][y]:
            size = sharks[pos[x][y]][4]
            del sharks[pos[x][y]]
            pos[x][y] = 0
            return size
    return 0
R,C,M = map(int,input().split())
 
sharks = {}
 
pos = [[0 for _ in range(C)] for _ in range(R)]
for num in range(1,M+1):
    x,y,speed,dire,size = map(int,input().split())
    x -= 1
    y -= 1
    dire -= 1
    sharks[num] = (x,y,speed,dire,size)
    pos[x][y] = num
 
 
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
    if len(sharks)==0:
        break
    result += fishing(y)
    next_pos = [[0 for _ in range(C)] for _ in range(R)]
    eaten = []
    for num in sharks:
        shark_x,shark_y,speed,dire,size = sharks[num]
        nx = shark_x + dx[dire]*speed
        ny = shark_y + dy[dire]*speed
        if dire in [0,1]:
            while not(0<=nx<R):
                if nx<0:
                    nx = -nx
                    dire = reverse[dire]
                else:
                    nx = (R-1)-(nx-(R-1))
                    dire = reverse[dire]
        else:
            while not(0<=ny<C):
                if ny<0:
                    ny = -ny
                    dire = reverse[dire]
                else:
                    ny = (C-1)-(ny-(C-1))
                    dire = reverse[dire]
 
 
        if next_pos[nx][ny] != 0:
            prev_shark_num = next_pos[nx][ny]
            if sharks[prev_shark_num][4] < size:
                next_pos[nx][ny] = num
                sharks[num] = (nx,ny,speed,dire,size)
                eaten.append(prev_shark_num)
            else:
                eaten.append(num)
 
        else:
            next_pos[nx][ny] = num
            sharks[num] =  (nx,ny,speed,dire,size)
    for num in eaten:
        del sharks[num]
    pos = [row[:] for row in next_pos]
 
print(result)

이 풀이는 상어의 정보를 저장하는 딕셔너리와 상어의 위치를 알 수 있는 리스트를 통해 관리를 해서 푸는 방식이다.

import sys
 
def input():
    return sys.stdin.readline()
 
N,M = map(int,input().split())
 
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]
 
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
 
    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        cnt[X] += cnt[Y]
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
dire = {
    "U": [-1,0],
    "L": [0,-1],
    "R" : [0, 1],
    'D': [1,0]
}
 
arr = [list(input()) for _ in range(N)]
make_set = [i for i in range(N*M+1)]
ranks = [1 for _ in range(N*M+1)]
cnt = [1 for _ in range(N*M+1)]
ranks[N*M] = float('inf')
 
for x in range(N):
    for y in range(M):
        point = x*M+y
        dx,dy = dire[arr[x][y]]
        nx = x + dx
        ny = y + dy
 
        if 0<=nx<N and 0<=ny<M:
            next_point = (x+dx)*M+y+dy
            union(point,next_point)
        else:
            union(point,N*M)
print(cnt[N*M]-1)

boj.kr/16724 와 동일한 방식으로 풀었다.

그러니깐 미로를 탈출 즉 범위를 벗어나는 경우를 N*M일때로 지정을 해주고, ranks를 최대로 준뒤

무조건 외각이 되었을때 외각이 부모가 되도록 만들어줬다.

주어진 미로의 크기는 N*M인데, N*M + 1 만큼의 make_set과 ranks, cnt를 만들어주고,

미로의 범위 내 이면 두개의 점을 union을 해주고,

범위 밖이면 우리가 만들어놓은 N*M에 union을 해주게 했다.

그리고 마지막에 cnt[N*M]에서 -1을 해주면 전체에서 탈출할 수 있는 칸의 수가 나오게 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
    if X !=Y:
        if ranks[X] < ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
 
def connect(r1,r2):
    if (r1['x1'] > r2['x1'] and r1['y1'] > r2['y1']   and r1['x2'] < r2['x2']  and r1['y2'] < r2['y2']):
        return False
    if (r1['x1'] < r2['x1'] and r1['y1'] < r2['y1']   and r1['x2'] > r2['x2']  and r1['y2'] > r2['y2']):
        return False
    if (r2['x1'] > r1['x2'] or r2['x2'] < r1['x1'] or r2['y1'] > r1['y2'] or r2['y2'] < r1['y1']):
        return False
    return True
N = int(input())
 
rect = [{
        'x1' : 0,
        'x2' : 0,
        'y1' : 0,
        'y2' : 0
    }]
for _ in range(N):
    x1,y1,x2,y2 = map(int,input().split())
    rect.append({
        'x1' : x1,
        'x2' : x2,
        'y1' : y1,
        'y2' : y2
    })
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
 
 
for i in range(N+1):
    for j in range(N+1):
        if i != j and connect(rect[i],rect[j]):
            if find_parents(i) != find_parents(j):
                union(i,j)
 
 
for ind in range(N):
    find_parents(ind)
 
 
print(len(set(make_set))-1)

어려웠던 문제였다. 이 문제를 푸는 방법은 사각형끼리 겹쳐있는지 아닌지를 판별을 해주고, 안 겹친 사각형이 총 몇개인지 세면 되는 문제였다.

단 거북이는 0,0 부터 시작하므로 0,0,0,0 으로 된 사각형이 있다고 가정하에 union find를 진행해주면 되는 문제였다.

import sys
def input():
    return sys.stdin.readline().rstrip()
N,M,R = map(int,input().split())
arr = [0] + list(map(int,input().split()))
 
graph = [{} for _ in range(N+1)]
 
 
INF = float('inf')
distance = [[0 if i == j else INF for j in range(N+1)] for i in range(N+1)]
for _ in range(R):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')), pay)
    graph[y][x] = min(graph[y].get(x, float('inf')),pay)
    distance[x][y] = min(distance[x][y],pay)
    distance[y][x] = min(distance[y][x],pay)
 
value = [0 for _ in range(N+1)]
for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance[start][end] > distance[start][mid] + distance[mid][end]:
                distance[start][end] =  distance[start][mid] + distance[mid][end]
 
 
result = 0
for node in range(1,N+1):
    temp = 0
    for next_node in range(1,N+1):
        if distance[node][next_node] <= M:
            temp += arr[next_node]
    if temp > result:
        result = temp
print(result)

이 문제는 플로이드와샬을 통해 최단거리를 갱신해주고, 

N^2를 탐색하면서, 거리가 M 이하일때 더해줘서 최대값을 갱신해서 출력해주는 문제이다.

import sys
 
 
def input():
    return sys.stdin.readline().rstrip()
 
 
def find_parents(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parents(make_set[ind])
    return make_set[ind]
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
    if ranks[X] < ranks[Y]:
        X,Y = Y,X
    make_set[Y] = X
    if ranks[X] == ranks[Y]:
        ranks[X] += 1
 
 
N,M = map(int,input().split())
 
arr = [0] + list(input().split())
weight_list = []
for _ in range(M):
    x,y,pay = map(int,input().split())
    if arr[x] != arr[y]:
        weight_list.append((pay,x,y))
 
weight_list.sort(reverse=True)
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
 
cnt = 0
result = 0
while weight_list:
    pay,x,y = weight_list.pop()
    X,Y = find_parents(x), find_parents(y)
 
    if X != Y:
        union(X,Y)
        cnt += 1
        result += pay
    if cnt == N-1:
        break
 
if cnt != N-1:
    print(-1)
else:
    print(result)

이 문제는 처음부터 간선을 저장할때 두 노드가 남초+여초인 조합인 경우에만 저장을 해서 크루스칼을 해주면 된다.

그리고 크루스칼을 진행하고, 전체 cnt의 개수가 N-1이 안되는 경우에는 전부 연결이 안되는 경우이니 -1을 출력해주고

같을 때에는 result를 출력해주면 된다.

def Innerbound(x,y):
    if 0<=x<N and 0<=y<M:
        return True
    else:
        return False
 
def dfs(idx,bit,total):
    global result
    if bit == 2**(N*M)-1:
        result = max(result,total)
        return
    else:
        if 2**idx&bit:
            dfs(idx+1,bit,total)
        else:
            x,y = idx//M, idx%M
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx + 1
                    ny = ny
                else:
                    break
            for rx in range(nx-1,x-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = rx*M + y
                temp_bit = temp_bit^(2**next_idx)
                visited[rx][y] = True
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx
                    ny = ny + 1
                else:
                    break
            for ry in range(ny-1,y-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = x*M + ry
                temp_bit = temp_bit^(2**next_idx)
                visited[x][ry] = True
 
 
N,M = map(int,input().split())
 
arr = [list(map(int,list(input()))) for _ in range(N)]
 
visited = [[True for _ in range(M)] for _ in range(N)]
result = 0
dfs(0,0,0)
print(result)

처음에 모든 경우들을 각각 하나씩 그려보면서 dfs를 해주었다.

가로 혹은 세로로 최대한 세울 수 있는 직사각형을 그려주고 그때부터 dfs를 하고 하나씩 내려주면서 dfs를 해주었다.

이 방식은 오래걸리는 방식이였고, 다른 사람들의 풀이를 보고 다시 푼 방식은 다음과 같다.

N,M = map(int,input().split())
 
arr = [list(map(int,list(input()))) for _ in range(N)]
result = 0
# 0은 가로인걸로 1은 세로인걸로 판별
for bit_shape in range(2**(N*M)):
    total_sum = 0
    for x in range(N):
        sub_sum = 0 # 작은 단위의 SUM
        for y in range(M):
            idx = x*M + y
            if not bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    
    for y in range(M):
        sub_sum = 0
        for x in range(N):
            idx = x*M + y
            if bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    result = max(result,total_sum)
print(result)

이 방식은 모든 경우를 먼저 구하는 거다. 이 문제는 최대 16개의 칸을 가지는 것이다.

이것을 비트로 표현해서 0이면 가로로 그려진 직사각형 1이면 세로인 직사각형으로 구분을 해주는것이다.

그러면 우리는 2**(N*M)의 경우의 수를 가질수 있다. 최대 65536가지이므로, 빠르게 구할 수 있다.

비트로 현재 종이조각의 상태를 구분하고, 그 상태에 맞게 숫자를 세서 최대값을 구하면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
def union(a,b):
    A = find_parent(a)
    B = find_parent(b)
    if A != B:
        if rank[A] < rank[B]:
            A,B = B,A
        make_set[B] = A
        if rank[A] == rank[B]:
            rank[A] += 1
        return True
    return False
 
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]
 
def kruskal():
    value = 0
    for p,x,y, in weight_list:
        if union(x,y):
            value += 1^p
    return value
 
 
N,M = map(int,input().split())
weight_list = []
for _ in range(M+1):
    x,y,p = map(int,input().split())
    weight_list.append((p,x,y))
make_set = list(range(N+1))
rank = [1]*(N+1)
weight_list.sort()
a = kruskal()
weight_list.sort(reverse=True)
make_set = list(range(N+1))
rank = [1]*(N+1)
b = kruskal()
print(a**2-b**2)

이 문제는 크루스칼을 활용해서 풀면 되는 문제이고, 크루스칼에 사용되는 간선을 오름차순과 내림차순으로 각각 정렬해서 

그때 크루스칼을 해서 값을 구한뒤 제곱값을 빼주면딘다.