Coding 공부

# 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까지 반복문을 돌려주면 차례대로 이동하는 것이 된다.

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

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


n,m,k = map(int,input().split())

fireball = {}

for _ in range(m):
    temp = list(map(int,input().split()))
    fireball[(temp[0]-1,temp[1]-1)] = []
    # 질량, 속도, 방향
    fireball[(temp[0]-1,temp[1]-1)].append([temp[2],temp[3],temp[4]])


for _ in range(k):
    new_fireball = {}
    for ind,vals in fireball.items():
        for val in vals:
            new_x = (ind[0] + val[1]*dx[val[2]])%n
            new_y = (ind[1] + val[1]*dy[val[2]])%n

            if new_fireball.get((new_x,new_y)):
                new_fireball[(new_x,new_y)].append([val[0],val[1],val[2]])
            else:
                new_fireball[(new_x,new_y)] = [[val[0],val[1],val[2]]]
    fireball ={}
    for ind,vals in new_fireball.items():
        if len(vals) > 1:
            total_weight = 0
            total_speed = 0
            total_direction = []
            for val in vals:
                total_weight += val[0]
                total_speed += val[1]
                total_direction.append(val[2])
            next_weight = total_weight//5
            next_speed = total_speed//len(vals)
            if next_weight:
                total_direction = list(map(lambda x: x%2 ,total_direction))
                if sum(total_direction) == 0 or sum(total_direction) == len(vals):
                    next_direction = [0,2,4,6]
                else:
                    next_direction = [1,3,5,7]
                fireball[ind] = []
                for i in range(4):
                    fireball[ind].append([next_weight,next_speed,next_direction[i]])

        else:
            fireball[ind] = vals

result = 0
for ind,vals in fireball.items():
    for val in vals:
        result += val[0]
print(result)

문제에 나온 내용을 그대로 시뮬레이션을 해주면 되는 것이었다.

이러한 무한의 길이를 가진 행렬문제나, 한 위치에 여러가지 정보를 저장해야하는 경우가

나오면 리스트로 구현하기 보단, 딕셔너리로 해서 위치좌표를 키로 지정하고 밸류 값에 여러가지 정보를 저장하는 방식을 선호한다.

이 문제에서 주의해야할 점은 행렬의 범위를 벗어나면 반대편으로 나오는 것이다. 

이 부분은 나는 n으로 나눈 나머지로 해결했다. 그 뒤에는 딕셔너리에 저장된 값 중 길이가 2 이상인 경우에는 문제에서 주어졌던 조건에 맞추어, 분리가 되도록 구현했다.

direction = [0,1,2,3]
# dire의 값이 0 : 좌
#  1: 하
#  2: 우
#  3: 상
move_dire = [[0,-1],
[1,0],
[0,1],
[-1,0]]
# 토네이도가 부는 방향 좌 하 우 상
#  -90도 회전 list(zip(*tornado))[::-1]
tornado = [[0,0,2,0,0],
[0,10,7,1,0],
[5,0,0,0,0],
[0,10,7,1,0],
[0,0,2,0,0]]



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

k = N**2 -1
cnt = 0
number_cnt = 1 
# number_cnt는 현재 방향으로 진행되는 최대거리를 알려주는 것이다.
double_cnt = 0
# 최대거리가 진행되는 횟수를 알려주는 것이다.
cur_cnt = 0
# 현재 이동 횟수이다.
cur_dire = 0 
# 현재 진행 방향이다.
# 이 문제에서 보면 알 수 있듯이, 좌하우상 순서로 진행되면 그 거리는 1,1,2,2,3,3,4,4,5,5,6,6 순으로 진행된다.
# 최대거리가 동일한게 2번 반복되는 것을 알 수 있다.
location = [N//2,N//2]
result = 0

while True:
    # 최대 거리와 현재 이동거리가 같다면 방향이 바뀌어야하는 것이므로, 방향을 바꾸면서 최대거리를 갱신해주는 작업을 해준다.
    if cur_cnt == number_cnt:
        cur_cnt = 0
        double_cnt += 1
        cur_dire = (cur_dire+1)%4
        tornado = list(zip(*tornado))[::-1]
        # -90도 회전을 해주는 간편한 방법이다. 
        if double_cnt == 2:
            # double_cnt가 2라는 것은 최대 이동거리가 동일한게 2번 반복된것이니, 최대 이동거리를 증가시켜줘야한다.
            double_cnt = 0
            number_cnt += 1
    # target_location은 현재 토네이도의 위치인 x에서 y로 갈때 y의 위치이다.
    target_location = [location[0]+move_dire[cur_dire][0],location[1]+move_dire[cur_dire][1]]
    # total_more는 targetloaction에 있는 모래의 양이다.
    total_more = arr[target_location[0]][target_location[1]]
    # torandao로 이동하는 것을 해주는 것이다.
    for i in range(5):
        for j in range(5):
            move_ind = [target_location[0]+i-2,target_location[1]+j-2]
            more = int(tornado[i][j]*arr[target_location[0]][target_location[1]]/100)
            if 0<=move_ind[0]<N and 0<=move_ind[1]<N:
                arr[move_ind[0]][move_ind[1]] += more
            # 만약 범위를 벗어나면, 결과값에 추가해준다.
            else:
                if more:
                    result += more
            # 흩날리고 남은 모래를 a의 모래가 되므로 구해준다.
            total_more -= more
    cur_cnt += 1
    last_location = [location[0]+2*move_dire[cur_dire][0],location[1]+2*move_dire[cur_dire][1]]
    # a의 위치가 범위를 벗어나면, result에 추가해주고, 아니면 해당위치에 모래를 추가해준다.
    if 0<=last_location[0]<N and 0<=last_location[1]<N:
        arr[last_location[0]][last_location[1]] += total_more
    else:
        result += total_more
    location = [location[0]+move_dire[cur_dire][0],location[1]+move_dire[cur_dire][1]]
    arr[location[0]][location[1]] = 0
    if location[0] == 0 and location[1] == 0:
        break
print(result)

 처음 풀었던 방식은 문제에 나와있는걸 그대로 구현해주었다.

이 문제를 풀때 중요한것은 방향전환과 그 반복성이 어떻게 진행되는지 찾아주고 그것을 구현해주는 방식이다.

하지만 코드길이가 길고, 변수도 많아서 문제를 풀때 헷갈리는게 많았다.

import sys

def blowSand(x,y,dire):
    global N
    ret = 0
    init_sand = arr[x][y]
    for i in range(10):
        if i == 9:
            sand = arr[x][y]
        else:
            sand = int(init_sand * rate[i]/100)
            arr[x][y] -= sand
        move_x = x + blowx[dire][i]
        move_y = y + blowy[dire][i]

        if 0<=move_x<N and 0<=move_y<N:
            arr[move_x][move_y] += sand
        else:
            ret += sand
    arr[x][y] = 0
    return ret

dx = [0,1,0,-1]
dy = [-1,0,1,0]
rate = [1, 1, 7, 7, 10, 10, 2, 2, 5]

blowx = [[-1, 1, -1, 1, -1, 1, -2, 2, 0,0], #left
[-1, -1, 0, 0, 1, 1, 0, 0, 2,1],   #down
[-1, 1, -1, 1, -1, 1, -2, 2, 0,0], #right
[1, 1, 0, 0, -1, -1, 0, 0, -2,-1],]  #up

blowy = [[1, 1, 0, 0, -1, -1, 0, 0, -2,-1],  #left
[-1, 1, -1, 1, -1, 1, -2, 2, 0,0], #down
[-1, -1, 0, 0, 1, 1, 0, 0, 2,1],   #right
[-1, 1, -1, 1, -1, 1, -2, 2, 0,0]] #up
N = int(sys.stdin.readline())
arr =[list(map(int,sys.stdin.readline().split())) for _ in range(N)]
x,y = N//2,N//2
i = 1
dire = 0
result = 0
while i<=N:
    j = 0
    while j <int(i):
        x = x + dx[dire%4]
        y = y + dy[dire%4]
        result += blowSand(x,y,dire%4)
        j += 1
    dire += 1
    i += 0.5
print(result)

위의 코드는 클론코딩한 것으로, 기본적인 원리는 위와 비슷하지만 좀 더 깔끔해서 보기가 편하다.

모래방향에 따른 x,y의 이동값을 전부 저장해준다. 그리고 그에 맞게 이동시 날라가는 비율을 적어준다.

여기서는 위에서 내가 했던 double_cnt 같은 것을 이용하지 않고 0.5 단위로 i의 값을 올려주고, 그것을 int화 함으로서 2번반복을 구현해냈다.

blowSand라는 함수를 통해, 날라간 모래 양을 계속 더해주고, 모래가 날라간 상황을 만들어줬다.

T = int(input())

dx = [-2,-1,1,2,2,1,-1,-2]

dy = [-1,-2,-2,-1,1,2,2,1]

for tc in range(T):

    l = int(input())

    array = [list(map(int,input().split())) for _ in range(2)]



    start = array[0][:]

    end = array[1][:]

    if start == end:

        print(0)

    else:

        result = 0

        visited = [[0]*l for _ in range(l)]

        visited[start[0]][start[1]] = 1

        stack = []

        stack.append((start[0],start[1],0))

        while stack:

            x,y,cnt = stack.pop(0)

            if x == end[0] and y == end[1]:

                result = cnt

                break

            for i in range(8):

                nx = x + dx[i]

                ny = y + dy[i]

                if 0<=nx<l and 0<=ny<l:

                    if not visited[nx][ny]:

                        visited[nx][ny] = 1

                        stack.append((nx,ny,cnt+1))

        print(result)

BFS를 이용해서 거리 변수만 추가해주면 되는 문제였다.