원자 충돌

https://www.codetree.ai/training-field/frequent-problems/problems/atom-collision/submissions?page=2&pageSize=20 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

요즘은 테스트케이스를 주지 않는 곳이 많다보니 오답노트를 써서 부족한 점을 차차 보완하려 합니다. ㅠㅠㅠ

 

간만에 시뮬했더니 머리에 쥐가....

 

1차 실패 - graph를 초기화 하는 걸 잊었어요. 

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

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

graph = [[[] for _ in range(n)] for _ in range(n)]

atomInfos = []

for i in range(m):
    y, x, m, s, d = list(map(int, input().split()))
    atomInfos.append([y-1,x-1,m,s,d])

def atom_move(y, x, m, s, d):
    global graph, dy, dx
    ny = (y + (n * 250) + (dy[d] * s)) % n
    nx = (x + (n * 250) + (dx[d] * s)) % n
    graph[ny][nx].append([ny, nx, m, s, d])

def atom_moves():
    global atomInfos
    for y, x, m, s, d in atomInfos:
        atom_move(y, x, m, s, d)

def add_atoms_info(moved_atom_infos):
    global atomInfos
    flag = moved_atom_infos[0][4] % 2
    total_m = 0
    total_s = 0

    for y, x, m, s, d in moved_atom_infos:
        total_m += m
        total_s += s

    nm = total_m // 5
    ns = total_s // len(moved_atom_infos)

    if nm == 0: #질량이 0 이면 소멸 됩니다.
        return 
    for y, x, m, s, d in moved_atom_infos:
        if flag != d % 2:
            for nd in [1, 3, 5 ,7]:
                atomInfos.append([y, x, nm, ns, nd])
            return 
    for nd in [0, 2, 4, 6]:
        atomInfos.append([y, x, nm, ns, nd])
    return 
    
def atom_synthesis():
    global graph, n, atomInfos
    for y in range(n):
        for x in range(n):
            if len(graph[y][x]) >= 2: #원자가 둘 이상이라면 합성
                add_atoms_info(graph[y][x])
            elif len(graph[y][x]) == 1: #원자가 하나라면 그래도 더함
                atomInfos.append(graph[y][x])

def cal_total_m(atomInfos):
    total_m = 0
    for y, x, m, s, d in atomInfos:
        total_m += m
    print(total_m)


for _ in range(k): #매초 마다 실행
    atom_moves()
    atomInfos = [] #원자 정보 초기화
    atom_synthesis()

cal_total_m(atomInfos)

 

2차 실패 - 원자는 한 개 인데 배열 째로 넘김.

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

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

graph = [[[] for _ in range(n)] for _ in range(n)]

atomInfos = []

for i in range(m):
    y, x, m, s, d = list(map(int, input().split()))
    atomInfos.append([y-1,x-1,m,s,d])

def atom_move(y, x, m, s, d):
    global graph, dy, dx
    ny = (y + (n * 250) + (dy[d] * s)) % n
    nx = (x + (n * 250) + (dx[d] * s)) % n
    graph[ny][nx].append([ny, nx, m, s, d])

def atom_moves():
    global atomInfos
    for y, x, m, s, d in atomInfos:
        atom_move(y, x, m, s, d)

def add_atoms_info(moved_atom_infos):
    global atomInfos
    flag = moved_atom_infos[0][4] % 2
    total_m = 0
    total_s = 0

    for y, x, m, s, d in moved_atom_infos:
        total_m += m
        total_s += s

    nm = total_m // 5
    ns = total_s // len(moved_atom_infos)

    if nm == 0: #질량이 0 이면 소멸 됩니다.
        return 
    for y, x, m, s, d in moved_atom_infos:
        if flag != d % 2:
            for nd in [1, 3, 5 ,7]:
                atomInfos.append([y, x, nm, ns, nd])
            return 
    for nd in [0, 2, 4, 6]:
        atomInfos.append([y, x, nm, ns, nd])
    return 
    
def atom_synthesis():
    global graph, n, atomInfos
    for y in range(n):
        for x in range(n):
            if len(graph[y][x]) >= 2: #원자가 둘 이상이라면 합성
                add_atoms_info(graph[y][x])
            elif len(graph[y][x]) == 1: #원자가 하나라면 그래도 더함
                atomInfos.append(graph[y][x])

def cal_total_m(atomInfos):
    total_m = 0
    for y, x, m, s, d in atomInfos:
        total_m += m
    print(total_m)


for _ in range(k): #매초 마다 실행
    atom_moves()
    atomInfos = [] #원자 정보 초기화
    atom_synthesis()
    graph = [[[] for _ in range(n)] for _ in range(n)] # 그래프 초기화
cal_total_m(atomInfos)

 

3차 - 성공

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

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

graph = [[[] for _ in range(n)] for _ in range(n)]

atomInfos = []

for i in range(m):
    y, x, m, s, d = list(map(int, input().split()))
    atomInfos.append([y-1,x-1,m,s,d])

def atom_move(y, x, m, s, d):
    global graph, dy, dx
    ny = (y + (n * 250) + (dy[d] * s)) % n
    nx = (x + (n * 250) + (dx[d] * s)) % n
    graph[ny][nx].append([ny, nx, m, s, d])

def atom_moves():
    global atomInfos
    for y, x, m, s, d in atomInfos:
        atom_move(y, x, m, s, d)

def add_atoms_info(moved_atom_infos):
    global atomInfos
    flag = moved_atom_infos[0][4] % 2
    total_m = 0
    total_s = 0

    for y, x, m, s, d in moved_atom_infos:
        total_m += m
        total_s += s

    nm = total_m // 5
    ns = total_s // len(moved_atom_infos)

    if nm == 0: #질량이 0 이면 소멸 됩니다.
        return 

    for y, x, m, s, d in moved_atom_infos:
        if flag != d % 2:
            for nd in [1, 3, 5 ,7]:
                atomInfos.append([y, x, nm, ns, nd])
            return 
    for nd in [0, 2, 4, 6]:
        atomInfos.append([y, x, nm, ns, nd])
    return 
    
def atom_synthesis():
    global graph, n, atomInfos
    for y in range(n):
        for x in range(n):
            if len(graph[y][x]) >= 2: #원자가 둘 이상이라면 합성
                add_atoms_info(graph[y][x])
            elif len(graph[y][x]) == 1: #원자가 하나라면 그래도 더함
                atomInfos.append(graph[y][x][0])

def cal_total_m(atomInfos):
    total_m = 0
    for y, x, m, s, d in atomInfos:
        total_m += m
    print(total_m)


for _ in range(k): #매초 마다 실행
    atom_moves()
    atomInfos = [] #원자 정보 초기화
    atom_synthesis()
    graph = [[[] for _ in range(n)] for _ in range(n)] # 그래프 초기화
cal_total_m(atomInfos)