Coding 공부

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을 구하고, 경로탐색을 통해 서로 이어진 숫자와 팀의 길이와 같은지 구분을 하고, 게리멘더링이 성립되는경우에 두 팀간의 격차를 구하고, 최소값을 갱신해준다.

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


def check(x,y):
    global N,M,max_value
    another_matrix = [[[0,-1],[0,0],[0,1],[1,0]],
    [[0,-1],[0,0],[0,1],[-1,0]],
    [[-1,0],[1,0],[0,0],[0,1]],
    [[-1,0],[1,0],[0,0],[0,-1]]]
    for tus in another_matrix:
        flag = True
        temp = 0
        for cx,cy in tus:
            nx = x + cx
            ny = y + cy
            if 0<= nx <N and 0<= ny<M:
                temp += arr[nx][ny]
            else:
                flag = False
                break
        if flag:
            if max_value < temp:
                max_value = temp
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)]
visted = [[0]*M for _ in range(N)]
max_value = 0
for x in range(N):
    for y in range(M):
        visted[x][y] = 1
        dfs(x,y,arr[x][y],1)
        visted[x][y] = 0
        check(x,y)


print(max_value)

BFS가 아니라 DFS를 이용해서 해야한다. DFS를 이용해서 하면, ㅗ 모양을 제외하고는 전부 추적이 가능하다.

그 부분만 따로 검증하면 된다. 길이가 3일때 검증하면 된다.

import sys
def dfs(x,y,result,total):
    global N,M,max_value
    if visited[x][y]:
        return
    if len(total) == 4:
        if max_value < result:
            max_value = result
        return
    visited[x][y] = 1
    for i in range(3):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < N and 0 <= ny <M:
            if not visited[nx][ny]:
                dfs(nx,ny,result+arr[nx][ny],total+[(nx,ny)])
    if len(total) == 3:
        center_x,center_y = total[1]
        for i in range(4):
            nx = center_x + dx[i]
            ny = center_y + dy[i]
            if 0<= nx < N and 0 <=ny<M:
                if not visited[nx][ny]:
                    dfs(nx,ny,result+arr[nx][ny],total+[(nx,ny)])
    visited[x][y] = 0
    return



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

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


arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
max_value = 0
for x in range(N):
    for y in range(M):
        dfs(x,y,arr[x][y],[(x,y)])
print(max_value)

이게 좀 더 깔끔한 코드이다.

def bfs(x,y,color):
    global puyo,visited,arr
    temp = [[x,y]]
    stack = [[x,y]]
    while stack:
        sx,sy = stack.pop(0)
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if 0<= nx < 12 and 0 <= ny <6:
                if arr[nx][ny] == color and visited[nx][ny]:
                    visited[nx][ny] = 0
                    stack.append([nx,ny])
                    temp.append([nx,ny])
    if len(temp) >= 4:
        return temp
    else:
        return []




arr = [list(input()) for _ in range(12)]
times = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while True:
    visited= [[1]*6 for _ in range(12)]
    puyo = []
    for x in range(12):
        for y in range(6):
            if arr[x][y] != '.' and visited[x][y]:
                visited[x][y] = 0
                check = bfs(x,y,arr[x][y])
                if check:
                    for x,y in check:
                        puyo.append((x,y))
    for x,y in puyo:
        arr[x][y] = '.'
    if len(puyo) == 0:
        break
    new_arr = [['.']*6 for _ in range(12)]
    for y in range(6):
        temp = []
        for x in range(11,-1,-1):
            if arr[x][y] != '.':
                temp.append(arr[x][y])
        for i in range(len(temp)):
            new_arr[11-i][y] = temp[i]
    arr = [row[:] for row in new_arr]
    times += 1
print(times)

 이 문제는 한단계씩 BFS를 돌려서 이어진 뿌요를 찾고, 그 뿌요가 하나도 없으면 멈추면 된다.

# R,C 비어있는곳 . 물이 차있는 * 비버의 굴 d 고슴도치S 돌은 X



R,C = map(int,input().split())

arr = [list(input()) for _ in range(R)]
gos = []
end = []
water = []
visited = [[1] * C for _ in range(R)]
for x in range(R):
    for y in range(C):
        if arr[x][y] != '.' and arr[x][y] != 'X':
            if arr[x][y] == 'S':
                gos.append((x,y,0))
                visited[x][y] = 0
            elif arr[x][y] == 'D':
                end.extend((x,y))
            else:
                water.append((x,y))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
flag = False
water_time = - 1
while gos:
    x,y,time = gos.pop(0)
    if x == end[0] and y == end[1]:
        result = time
        flag = True
        break
    if water_time < time:
        new_water = []
        for wx,wy in water:
            for i in range(4):
                wnx = wx + dx[i]
                wny = wy + dy[i]
                if 0<= wnx <R and 0<= wny <C:
                    if arr[wnx][wny] == '.':
                        new_water.append((wnx,wny))
                        arr[wnx][wny] = '*'
        water_time += 1
        water = [row[:] for row in new_water]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < R and 0<= ny < C and visited[nx][ny]:
            if arr[nx][ny] == '.' or arr[nx][ny] == 'D':
                visited[nx][ny] = 0
                if nx == end[0] and ny == end[1]:
                    flag = True
                    result = time + 1
                    break
                gos.append((nx,ny,time+1))
    if flag:
        break
if flag:
    print(result)
else:
    print('KAKTUS')

BFS를 이용해서 문제를 푸는데 한가지만 조심해주면 된다. 물은 한번만 차오르고, 같은시간대에 고슴도치는 여러군데에 들릴수도 있으니, 물이 차오르는 특수조건을 주고, 그때에만 물이 번지는걸 유의해주면 된다.

import collections
N = int(input())
arr = list(map(int,input().split()))
a = collections.Counter(arr)
if max(a.values()) > 2 or  len(a.keys()) != max(a.keys())+1:
    print(0)
else:
    keys = sorted(a.keys())
    result = 1
    prev_cnt = a[0]
    flag = True
    onecnt = False
    for k in keys:

        if prev_cnt < a[k]:
            flag = False
            break
        else:
            prev_cnt = a[k]
            if a[k] == 2:
                result*=2
            else:
                onecnt = True
    if flag:
        if onecnt:
            print(result*2)
        else:    
            print(result)
    else:
        print(0)

이 문제는 경우의 수를 구해주면 된다. 

이 문제에서 중요한 것은, 연속되는 숫자들만 존재해야하고, 같은 숫자는 3개 이상이 되지 않으며,

뒤의 숫자의 개수가 앞의 숫자보다 많으면 안된다.

그리고 2개씩 존재하는 수의 개수만큼 2의 제곱승이 되고, 2개씩 존재하는 수 외에 1개씩 존재하는 수가 있으면, 2배를 해주면된다.

이 부분만 캐치해주면 코드로 구현해주면 된다.

위의 풀이는 조금 난잡하게 된 코드이다.

좀 더 깔끔한 코드는 밑에 올린다.

total = [0]*41
n = int(input())
arr = list(map(int,input().split()))
for num in arr:
    total[num] += 1
prev_cnt = 2
flag = False
for cnt in total:
    if cnt > prev_cnt:
        flag = True
        break
    prev_cnt = cnt

if flag:
    print(0)
else:
    result = 2**(total.count(2) + (1 in total))
    print(result)

import collections
dx=[-1,1,0,0]
dy=[0,0,1,-1]

def bfs(x,y,number):
    q=collections.deque()
    q.append([x,y])
    visited[x][y]=1
    arr[x][y]=number
    while q:
        ax,ay=q.popleft()
        for i in range(4):
            nx=ax+dx[i]
            ny=ay+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny]==1 and visited[nx][ny]==0:
                    q.append([nx,ny])
                    arr[nx][ny]=number
                    visited[nx][ny]=1

def find_min_distance(land_number):
    dist=[[-1]*M for _ in range(N)]
    q=collections.deque()
    for i in range(N):
        for j in range(M):
            if arr[i][j]==land_number:
                dist[i][j]=0
                q.append([i,j])

    while q:
        x,y=q.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if dist[nx][ny]:
                    distance=1
                    while True:
                        nx=nx+dx[i]
                        ny=ny+dy[i]
                        if nx<0 or nx>=N or ny<0 or ny>=M:
                            break
                        if dist[nx][ny]==0:
                            break
                        if 0<=nx<N and 0<=ny<M:
                            if arr[nx][ny]>0 and arr[nx][ny]!=land_number:
                                if distance>1:
                         
                                    min_distance[arr[nx][ny]][land_number]=min(min_distance[arr[nx][ny]][land_number],distance)
                                    min_distance[land_number][arr[nx][ny]]=min(min_distance[land_number][arr[nx][ny]],distance)
                                break
                        
                        
                        distance+=1





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

island=1
arr=[list(map(int,input().split())) for i in range(N)]
visited=[[0]*M for i in range(N)]
for i in range(N):
    for j in range(M):
        if arr[i][j]==1 and visited[i][j]==0:
            bfs(i,j,island)
            island+=1

min_distance=[[99999]*(island) for _ in range(island)]
for i in range(1,island):
    find_min_distance(i)

total_list=[]
for i in range(island):
    for j in range(island):
        if min_distance[i][j]!=99999:
            total_list.append([i,j,min_distance[i][j]])
total_list.sort(key= lambda x : x[2])

conneted_list=[0]*island
conneted_list[0]=1
conneted_list[1]=1

result=0
while sum(conneted_list)!=island:
    for total in total_list:
        start =total[0]
        end = total[1]
        value=total[2]
        if conneted_list[start] or conneted_list[end]:
            if conneted_list[start] and conneted_list[end]:
                continue
            else:
                conneted_list[start]=1
                conneted_list[end]=1
                result+=value
                break
    else:
        result=-1
        break

print(result)

 MST 알고리즘 문제이다. 이 문제가 mst라는지도 모르고 풀었었다.

각각의 섬들의 최소 거리들을 구해주고, 그것을 짧은거리를 기준으로 정렬을 해준다.

두 섬중 하나라도 연결되어 있어야하고, 만약 둘다 연결이 되어있는 상태면 이미 연결한 것이므로, 다음으로 넘어가고, 둘중 하나만 연결되어 있을 때, 다리를 놓아주고 그 값을 결과값에 더해준다. 그리고 다시 처음부터 시작해준다.

그리고 만약 break를 한번도 마주치지 않고, 반복문이 끝난거면 더 이상 연결될 섬이 없는 경우이므로 -1을 출력해주면 된다.

from collections import deque

def bfs(x):
    queue = deque()
    queue.append(x)
    distance[x] = 0
    while queue:
        now = queue.popleft()
        for next_node in graph[now]:
            if visited[next_node] == False:
                visited[next_node] = True
                if distance[next_node] == -1:
                    distance[next_node] = distance[now] + 1
                    queue.append(next_node)
                
                

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

distance = [-1] * (n + 1)
visited = [False] * (n + 1)

bfs(x)

result = []
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        result.append(i)
        check = True
if len(result):
    for i in range(len(result)):
        print(result[i])
else:
    print(-1)

 기초적인 다익스트라 문제이고, 다익스트라를 모르더라도 BFS를 아는 것만으로 풀 수 있다.

이 문제를 풀 시기에 다익스트라를 몰랐고, 현재도 다익스트라를 배웠지만 자주 안 쓰다보니 까먹었다!(다시 공부해야한다.)

이 문제는 단 방향 그래프이고, 방문 여부와 거리를 저장하기 위한 리스트를 만들어주었다.

bfs 를 통해 현재 위치에서 최단거리를 구하고, 이동거리를 저장하고 주어진 K와 같은 노드들을 출력해주면 된다.

n, k = list(map(int,input().split()))
conveyer = list(map(int,input().split()))
robot = [0]*n
robot_cnt = 1
step = 0
while conveyer.count(0) < k:
    last_number = conveyer.pop()
    conveyer.insert(0,last_number)
    last_robot = robot.pop()
    robot.insert(0,0)
    robot[n-1] = 0
    que = []
    for i in range(n):
        if robot[i] > 0:
            que.append([robot[i],i])
    que.sort()
    while que:
        robot_ind, ind = que.pop(0)
        if ind + 1 == n-1:
            if conveyer[n-1] != 0:
                robot[ind+1] = 0
                robot[ind] = 0
                conveyer[n-1] -= 1
            else:
                robot[ind] = robot_ind 
        else:
            if conveyer[ind+1] != 0 and robot[ind+1]==0:
                robot[ind+1] = robot_ind
                robot[ind] = 0
                conveyer[ind+1] -= 1
            else:
                robot[ind] = robot_ind
    if robot[0] == 0 and conveyer[0]:
        robot[0] = robot_cnt
        robot_cnt += 1
        conveyer[0] -= 1
    step += 1
print(step)

첫 풀이는 문제에서 robot에는 로봇의 최초진입시기를 저장해주고, conveyer에는 컨베이어의 내구도를 적어주는 것이다.

먼저 컨베이어 벨트가 움직이고 n-1 위치에 도착시 로봇이 바로 내려가는 것만 주의해주면 어렵지 않은 문제였다. 하지만 시간이 오래걸리는 문제가 있으므로, 밑의 방식으로 개선했다.

from collections import deque

n, k = map(int, input().split())
arr = list(map(int, input().split()))
ls = [['X'] for _ in range(2*n)]
for i in range(2*n):
    ls[i].append(arr[i])
belt = deque(ls)

lift_idx = 0
drop_idx = n-1
cnt = 0 
result = 0
while True:
    #내구도가 0인게 k개 이상인지 카운트해서 while문 탈출조건을 세워준다.
    if cnt >= k:
        break
    # 벨트 돌아가기
    tmp = belt.pop()
    belt.appendleft(tmp)
    # 내릴 수 있으면 내린다.
    if belt[drop_idx][0] == 'O':
        belt[drop_idx][0] = 'X'
    #이동이 가능하면 이동한다.
    for i in range(n-2,-1,-1):
        if belt[i][0] == 'O':
            if belt[i+1][0] == 'X' and belt[i+1][1] != 0:
                belt[i][0] = 'X'
                belt[i+1][0] = 'O'
                belt[i+1][1] -= 1
                if i+1 == drop_idx:
                   belt[i+1][0] = 'X'
    #로봇을 올린다.
    if belt[lift_idx][1] != 0 and belt[lift_idx][0] == 'X':
        belt[lift_idx][0] = 'O'
        belt[lift_idx][1] -= 1
    cnt = 0
    for i in range(len(belt)):
        if belt[i][1] == 0: 
            cnt += 1
    result += 1
                
print(result)

belt의 i번째는 해당 index에 로봇이 있는지 유무와 belt의 내구도를 저장해준다.

그리고 어차피 n-1에서 모든 로봇은 내려가므로, n-2 부터 0까지 반복문을 돌려주면 차례대로 이동하는 것이 된다.

이 부분만 바뀌고 나머지는 동일하다.