[백준 BOJ] 1385 벌집 (python)

문제 링크 : https://www.acmicpc.net/problem/1385

1385번: 벌집

저의 풀이는 시간복잡도를 줄이기 위해 좌표계 변환 후 BFS를 이용하는 방식이 아닌 복잡한 구현으로 풀이가 되었습니다.

코드에 대한 설명은 코드 길이 8379B의 긴 풀이라 구간별로 설명 드리도록 하겠습니다.

무엇보다 이 문제에서는 풀이보다는 풀어가는 아이디어에 대한 영감을 얻으시면 좋은 문제라고 생각합니다.

 

0. 전체 아이디어

 

입력값의 최대가 1,000,000인 만큼 BFS 풀이는 위험할 수 있다고 판단하였습니다.

따라서 벌집을 1과 1을 제외한 여섯 부분으로 나눈후 a와 b가 포함되어 있는 경우에 따라 케이스를 나눈 후 최단 거리 경로를 찾도록 구현하였습니다.

 

1. 그룹, 레벨 지정

a, b = map(int, input().split())
switch = False
if a > b:
    temp = a
    a = b
    b = temp
    switch = True
point = 2
add_n = 0
group = 0
level = 0
a_info = False
b_info = False
if a == 1:
    a_info = [1, 0]
if b == 1:
    b_info = [1, 0]
while not(a_info and b_info):
    add_n += 1
    level += 1
    for _ in range(6):
        if a >= point and a < point + add_n:
            a_info = [group % 6 + 2, level]
        if b >= point and b < point + add_n:
            b_info = [group % 6 + 2, level]
        group += 1
        point += add_n
chai = (b_info[0] - a_info[0]) % 6
max_level = b_info[1]

 

우선적으로 진행한 사항은 입력값 a, b를 group으로 묶고, level을 지정하는 것이였습니다.

group은 a, b가 포함된 구역을, level은 a, b가 1로부터 떨어진 정도를 나타내는 값입니다.

1은 group 1, level 0

2~7은 각 그룹의 level 1

8, 9는 group 2, level 2

10, 11은 group 3, level 2

...

가 되어가는 식입니다.

(추후 예시 그림 추가하도록 하겠습니다.)

이후 두 그룹의 차이값을 chai로, 최대 레벨을 max_level로 지정해 줍니다.

참고로 a, b는 편의를 위해 오름차순으로 설정해주었습니다. (switch로 순서가 변경되었는지 체크)

 

2. find_end 함수

def find_end(n, group, level, method):
    if group == 8:
        group = 2
    if group == 1:
        group = 7
    fronts = [group]
    add_n = group + 4
    for _ in range(max_level):
        fronts.append(fronts[-1] + add_n)
        add_n += 6
    backs = [group]
    add_n = group + 5
    for _ in range(max_level):
        backs.append(backs[-1] + add_n)
        add_n += 6
    # print(fronts, backs)
    ways = {}
    if method == 'front':
        line = []
        back_n = backs[level - 1] - n
        front_n = n - fronts[level - 1]
        for i in range(front_n + 1):
            line.append(backs[level - 1 - i] - back_n)
        # print(line)
        for i in range(level - front_n):
            ways[fronts[i]] = fronts[i:back_n] + line[::-1]
        for i in range(level - front_n, level):
            w = []
            for j in range(i - back_n):
                w.append(fronts[i] + j)
            ways[fronts[i]] = w + line[level - i - 1::-1]
        for i in range(level, max_level):
            ways[fronts[i]] = [fronts[i]] + ways[fronts[i - 1]]
        # pprint(ways)
    if method == 'back':
        line = []
        back_n = backs[level - 1] - n
        front_n = n - fronts[level - 1]
        for i in range(back_n + 1):
            line.append(fronts[level - 1 - i] + front_n)
        # print(line)
        for i in range(level - back_n):
            ways[backs[i]] = backs[i:front_n] + line[::-1]
        for i in range(level - back_n, level):
            w = []
            for j in range(i - front_n):
                w.append(backs[i] - j)
            ways[backs[i]] = w + line[level - i - 1::-1]
        for i in range(level, max_level):
            ways[backs[i]] = [backs[i]] + ways[backs[i - 1]]
        # pprint(ways)
    if method == 'line':
        ways[group] = [group]
        for i in range(1, max_level + 1):
            front = fronts[i]
            back = backs[i]
            ways[fronts[i]] = []
            ways[backs[i]] = []
            j = 0
            while j <= i:
                j += 1
                ways[fronts[i]].append(front)
                ways[backs[i]].append(back)
                front += 1
                back -= 1
        # pprint(ways)
    return ways

 

find_end는 n에서 그룹의 끝점과 연결되는 지점들이나 특정 level에 연결되는 점들을 찾아주는 함수입니다.

입력인자는 n, group, level, method으로 group은 n의 group, level은 n의 level, method는 'front', 'back', 'line'을 받습니다.

참고로 n이 1인 경우는 없으며 group이 1, 8로 입력되는 경우는 7, 2인 경우로 받게됩니다.

method가 'front'인 경우는 시계방향에서 1부터 max_level까지의 앞 쪽 끝들 부터 n까지의 최단 거리의 경로들을 return 합니다.

method가 'back'인 경우는 시계방향에서 1부터 max_level까지의 뒤 쪽 끝들 부터 n까지의 최단 거리의 경로들을 return 합니다.

group 2의 경우 앞 쪽 끝들(fronts)은 [2, 8, 20,...]이 되고 뒤 쪽 끝들(backs)은 [2, 9, 22,...]이 됩니다.

return되는 ways는 위의 끝 점들을 key로 두고 그 점으로부터 n까지의 최단 거리 경로를 value로 갖는 dictionary가 됩니다.

method가 'line'인 경우는 특수한 경우로 해당 group의 각 level의 끝 점에서 반대점까지 연결되는 경로들을 n과 level은 입력받을 필요가 없습니다.

 

3. fine_connect 함수

def find_connect(A, B):
    if B == 8:
        B = 2
    if A == 1:
        A = 7
    fronts = [B]
    add_n = B + 4
    for _ in range(max_level - 1):
        fronts.append(fronts[-1] + add_n)
        add_n += 6
    backs = [A]
    add_n = A + 5
    for _ in range(max_level - 1):
        backs.append(backs[-1] + add_n)
        add_n += 6
    ways = {}
    ways[fronts[0]] = [backs[0]]
    ways[backs[max_level - 1]] = [fronts[max_level - 1]]
    for i in range(max_level - 1):
        ways[backs[i]] = [fronts[i], fronts[i + 1]]
        ways[fronts[i + 1]] = [backs[i], backs[i + 1]]
    # pprint(ways)
    return ways

 

find_connect는 A그룹에서 B그룹 접하는 부분의 경로들을 찾는 함수입니다.

마찬가지로 group이 1, 8로 입력되는 경우는 7, 2인 경우로 받게됩니다.

입력되는 A그룹과 B그룹 시계방향으로 접해있어야 합니다.

각 끝 점을 key로 가지고 옆 그룹과 연결 가능한 점들을 value로 가지는 ways를 return하게 됩니다.

 

4. group 1이 포함된 경우

if b_info[0] == 1:
    print(1)

elif a_info[0] == 1:
    ways = find_end(b, b_info[0], b_info[1], 'front')
    answer = [1] + ways[b_info[0]]
    if switch:
        answer = answer[::-1]

 

b가 1인 경우는 a, b가 모두 1이므로 1이 답이 됩니다.

a가 1인 경우는 1과 find_end로 찾은 b의 경로 중 b의 그룹 번호(level 1)부터의 경로를 찾아주면 됩니다.

a, b가 switch된 경우는 역 경로를 구해주시면 됩니다.

 

5. 차이가 0인 경우 (그룹이 같은 경우)

elif chai == 0:
    fronts = find_end(a, a_info[0], a_info[1], 'front')
    backs = find_end(a, a_info[0], a_info[1], 'back')
    fronts = list(fronts.keys())
    backs = list(backs.keys())
    a_front_n = a - fronts[a_info[1] - 1]
    a_back_n = backs[a_info[1] - 1] - a
    b_front_n = b - fronts[b_info[1] - 1]
    b_back_n = backs[b_info[1] - 1] - b
    if a_front_n >= b_front_n:
        step = a_front_n - b_front_n
        answer = [a]
        for _ in range(step):
            answer.append(answer[-1] - 1)
        for i in range(a_info[1], b_info[1]):
            answer.append(fronts[i] + b_front_n)
    elif a_back_n >= b_back_n:
        step = a_back_n - b_back_n
        answer = [a]
        for _ in range(step):
            answer.append(answer[-1] + 1)
        for i in range(a_info[1], b_info[1]):
            answer.append(backs[i] - b_back_n)
    else:
        answer = [a]
        curve = False
        for i in range(a_info[1], b_info[1]):
            w1 = fronts[i] + a_front_n
            w2 = backs[i] - b_back_n
            if curve:
                answer.append(w2)
            else:
                answer.append(w1)
            if w1 == w2:
                curve = True
    if switch:
        answer = answer[::-1]

 

같은 그룹내 최단 거리는 사실 구현이 조금 많이 복잡합니다.

find_end는 그냥 그룹네 fronts, backs 지점을 알기 위해서만 사용하였습니다.

a, b의 같은 level상의 끝 점 에서부터의 거리르 계산해 최단 경로를 찾았다고 간략히 말할 수 있습니다.

사실 전체 아이디어에서 이 케이스를 크게 생각하지 못해 수학적으로 너무 복잡한 코드가 되고 말았습니다. (반성)

차이가 0이 아닌 이외 경우는 오히려 간단합니다.

 

6. 차이가 1, 5인 경우 (그룹이 인접한 경우)

elif chai == 1:
    backs = find_end(a, a_info[0], a_info[1], 'back')
    fronts = find_end(b, b_info[0], b_info[1], 'front')
    connects = find_connect(a_info[0], b_info[0])
    ways = {}
    for back in backs.keys():
        for w in connects[back]:
            way = backs[back][::-1] + [w]
            if w not in ways.keys() or len(way) < len(ways[w]):
                ways[w] = way
    answer = []
    for front in fronts.keys():
        ans = ways[front] + fronts[front][1:]
        if not answer or len(ans) < len(answer):
            answer = ans
    if switch:
        answer = answer[::-1]

elif chai == 5:
    fronts = find_end(a, a_info[0], a_info[1], 'front')
    backs = find_end(b, b_info[0], b_info[1], 'back')
    connects = find_connect(b_info[0], a_info[0])
    ways = {}
    for front in fronts.keys():
        for w in connects[front]:
            way = fronts[front][::-1] + [w]
            if w not in ways.keys() or len(way) < len(ways[w]):
                ways[w] = way
    answer = []
    for back in backs.keys():
        ans = ways[back] + backs[back][1:]
        if not answer or len(ans) < len(answer):
            answer = ans
    if switch:
        answer = answer[::-1]

 

 

시계방향으로 앞쪽인 경우의 backs들과 뒤쪽인 경우의 fronts들과 그 연결점인 connects를 조합하여 최단 거리인 경로를 찾아 주시면 됩니다.

 

7. 차이가 2, 4인 경우 (그룹을 하나 경유하는 경우)

elif chai == 2:
    backs = find_end(a, a_info[0], a_info[1], 'back')
    connects_1 = find_connect(a_info[0], a_info[0] + 1)
    line = find_end(_, a_info[0] + 1, _, 'line')
    connects_2 = find_connect(b_info[0] - 1, b_info[0])
    fronts = find_end(b, b_info[0], b_info[1], 'front')
    ways_1 = {}
    for back in backs.keys():
        for w in connects_1[back]:
            way = backs[back][::-1] + [w]
            if w not in ways_1.keys() or len(way) < len(ways_1[w]):
                ways_1[w] = way
    for key in ways_1.keys():
        ways_1[key] += line[key][1:]
    ways_2 = {}
    for key, lst in ways_1.items():
        for w in connects_2[lst[-1]]:
            way = ways_1[key] + [w]
            if w not in ways_2.keys() or len(way) < len(ways_2[w]):
                ways_2[w] = way
    answer = []
    for front in fronts.keys():
        ans = ways_2[front] + fronts[front][1:]
        if not answer or len(ans) < len(answer):
            answer = ans
    if switch:
        answer = answer[::-1]

elif chai == 4:
    fronts = find_end(a, a_info[0], a_info[1], 'front')
    connects_1 = find_connect(a_info[0] - 1, a_info[0])
    line = find_end(_, a_info[0] - 1, _, 'line')
    connects_2 = find_connect(b_info[0], b_info[0] + 1)
    backs = find_end(b, b_info[0], b_info[1], 'back')
    ways_1 = {}
    for front in fronts.keys():
        for w in connects_1[front]:
            way = fronts[front][::-1] + [w]
            if w not in ways_1.keys() or len(way) < len(ways_1[w]):
                ways_1[w] = way
    for key in ways_1.keys():
        ways_1[key] += line[key][1:]
    ways_2 = {}
    for key, lst in ways_1.items():
        for w in connects_2[lst[-1]]:
            way = ways_1[key] + [w]
            if w not in ways_2.keys() or len(way) < len(ways_2[w]):
                ways_2[w] = way
    answer = []
    for back in backs.keys():
        ans = ways_2[back] + backs[back][1:]
        if not answer or len(ans) < len(answer):
            answer = ans
    if switch:
        answer = answer[::-1]

 

시계방향으로 앞쪽인 경우의 backs들과 뒤쪽인 경우의 fronts들과 사이 그룹의 line과 그 연결점인 connects_1과 connects_2를 조합하여 최단 거리인 경로를 찾아 주시면 됩니다.

조합의 경우의 수가 다양해졌을 뿐이지 전 경우와 경로를 찾는 방법은 같습니다.

 

8. 차이가 3인 경우 (그룹이 마주보는 경우)

elif chai == 3:
    fronts = find_end(a, a_info[0], a_info[1], 'front')
    backs = find_end(b, b_info[0], b_info[1], 'back')
    answer = fronts[a_info[0]][::-1] + [1] + backs[b_info[0]]
    if switch:
        answer = answer[::-1]

print(*answer)

 

그룹이 마주보고 있는 경우는 간단하게 가운데 1을 경유하는 경로를 찾아주시면 됩니다.

이로써 최종적으로 answer가 최단 거리의 경로가 됩니다.

 

글을 쓰며 함수 내외에서 사용된 최단경로를 만드는 부분에 대해서는 수학적인 계산을 많이 사용하였을 뿐 좋은 알고리즘을 사용한 것은 아니기에 자세하게 설명할 필요는 없다고 생각하여 설명은 넘어갔습니다.

문제에 대한 아이디어와 그에 필요한 함수들을 어떻게 정하고 사용하였는지 위주로 글을 봐주셨으면 좋겠습니다.

 

최종 제출 코드 

def find_end(n, group, level, method):
    if group == 8:
        group = 2
    if group == 1:
        group = 7
    fronts = [group]
    add_n = group + 4
    for _ in range(max_level):
        fronts.append(fronts[-1] + add_n)
        add_n += 6
    backs = [group]
    add_n = group + 5
    for _ in range(max_level):
        backs.append(backs[-1] + add_n)
        add_n += 6
    # print(fronts, backs)
    ways = {}
    if method == 'front':
        line = []
        back_n = backs[level - 1] - n
        front_n = n - fronts[level - 1]
        for i in range(front_n + 1):
            line.append(backs[level - 1 - i] - back_n)
        # print(line)
        for i in range(level - front_n):
            ways[fronts[i]] = fronts[i:back_n] + line[::-1]
        for i in range(level - front_n, level):
            w = []
            for j in range(i - back_n):
                w.append(fronts[i] + j)
            ways[fronts[i]] = w + line[level - i - 1::-1]
        for i in range(level, max_level):
            ways[fronts[i]] = [fronts[i]] + ways[fronts[i - 1]]
        # pprint(ways)
    if method == 'back':
        line = []
        back_n = backs[level - 1] - n
        front_n = n - fronts[level - 1]
        for i in range(back_n + 1):
            line.append(fronts[level - 1 - i] + front_n)
        # print(line)
        for i in range(level - back_n):
            ways[backs[i]] = backs[i:front_n] + line[::-1]
        for i in range(level - back_n, level):
            w = []
            for j in range(i - front_n):
                w.append(backs[i] - j)
            ways[backs[i]] = w + line[level - i - 1::-1]
        for i in range(level, max_level):
            ways[backs[i]] = [backs[i]] + ways[backs[i - 1]]
        # pprint(ways)
    if method == 'line':
        ways[group] = [group]
        for i in range(1, max_level + 1):
            front = fronts[i]
            back = backs[i]
            ways[fronts[i]] = []
            ways[backs[i]] = []
            j = 0
            while j <= i:
                j += 1
                ways[fronts[i]].append(front)
                ways[backs[i]].append(back)
                front += 1
                back -= 1
        # pprint(ways)
    return ways

def find_connect(A, B):
    if B == 8:
        B = 2
    if A == 1:
        A = 7
    fronts = [B]
    add_n = B + 4
    for _ in range(max_level - 1):
        fronts.append(fronts[-1] + add_n)
        add_n += 6
    backs = [A]
    add_n = A + 5
    for _ in range(max_level - 1):
        backs.append(backs[-1] + add_n)
        add_n += 6
    ways = {}
    ways[fronts[0]] = [backs[0]]
    ways[backs[max_level - 1]] = [fronts[max_level - 1]]
    for i in range(max_level - 1):
        ways[backs[i]] = [fronts[i], fronts[i + 1]]
        ways[fronts[i + 1]] = [backs[i], backs[i + 1]]
    # pprint(ways)
    return ways

a, b = map(int, input().split())
switch = False
if a > b:
    temp = a
    a = b
    b = temp
    switch = True
point = 2
add_n = 0
group = 0
level = 0
a_info = False
b_info = False
if a == 1:
    a_info = [1, 0]
if b == 1:
    b_info = [1, 0]
while not(a_info and b_info):
    add_n += 1
    level += 1
    for _ in range(6):
        if a >= point and a < point + add_n:
            a_info = [group % 6 + 2, level]
        if b >= point and b < point + add_n:
            b_info = [group % 6 + 2, level]
        group += 1
        point += add_n
chai = (b_info[0] - a_info[0]) % 6
max_level = b_info[1]
if b_info[0] == 1:
    print(1)

elif a_info[0] == 1:
    ways = find_end(b, b_info[0], b_info[1], 'front')
    answer = [1] + ways[b_info[0]]
    if switch:
        answer = answer[::-1]

elif chai == 0:
    fronts = find_end(a, a_info[0], a_info[1], 'front')
    backs = find_end(a, a_info[0], a_info[1], 'back')
    fronts = list(fronts.keys())
    backs = list(backs.keys())
    a_front_n = a - fronts[a_info[1] - 1]
    a_back_n = backs[a_info[1] - 1] - a
    b_front_n = b - fronts[b_info[1] - 1]
    b_back_n = backs[b_info[1] - 1] - b
    if a_front_n >= b_front_n:
        step = a_front_n - b_front_n
        answer = [a]
        for _ in range(step):
            answer.append(answer[-1] - 1)
        for i in range(a_info[1], b_info[1]):
            answer.append(fronts[i] + b_front_n)
    elif a_back_n >= b_back_n:
        step = a_back_n - b_back_n
        answer = [a]
        for _ in range(step):
            answer.append(answer[-1] + 1)
        for i in range(a_info[1], b_info[1]):
            answer.append(backs[i] - b_back_n)
    else:
        answer = [a]
        curve = False
        for i in range(a_info[1], b_info[1]):
            w1 = fronts[i] + a_front_n
            w2 = backs[i] - b_back_n
            if curve:
                answer.append(w2)
            else:
                answer.append(w1)
            if w1 == w2:
                curve = True
    if switch:
        answer = answer[::-1]

elif chai == 1:
    backs = find_end(a, a_info[0], a_info[1], 'back')
    fronts = find_end(b, b_info[0], b_info[1], 'front')
    connects = find_connect(a_info[0], b_info[0])
    ways = {}
    for back in backs.keys():
        for w in connects[back]:
            way = backs[back][::-1] + [w]
            if w not in ways.keys() or len(way) < len(ways[w]):
                ways[w] = way
    answer = []
    for front in fronts.keys():
        ans = ways[front] + fronts[front][1:]
        if not answer or len(ans) < len(answer):
            answer = ans
    if switch:
        answer = answer[::-1]

elif chai == 2:
    backs = find_end(a, a_info[0], a_info[1], 'back')
    connects_1 = find_connect(a_info[0], a_info[0] + 1)
    line = find_end(_, a_info[0] + 1, _, 'line')
    connects_2 = find_connect(b_info[0] - 1, b_info[0])
    fronts = find_end(b, b_info[0], b_info[1], 'front')
    ways_1 = {}
    for back in backs.keys():
        for w in connects_1[back]:
            way = backs[back][::-1] + [w]
            if w not in ways_1.keys() or len(way) < len(ways_1[w]):
                ways_1[w] = way
    for key in ways_1.keys():
        ways_1[key] += line[key][1:]
    ways_2 = {}
    for key, lst in ways_1.items():
        for w in connects_2[lst[-1]]:
            way = ways_1[key] + [w]
            if w not in ways_2.keys() or len(way) < len(ways_2[w]):
                ways_2[w] = way
    answer = []
    for front in fronts.keys():
        ans = ways_2[front] + fronts[front][1:]
        if not answer or len(ans) < len(answer):
            answer = ans
    if switch:
        answer = answer[::-1]

elif chai == 3:
    fronts = find_end(a, a_info[0], a_info[1], 'front')
    backs = find_end(b, b_info[0], b_info[1], 'back')
    answer = fronts[a_info[0]][::-1] + [1] + backs[b_info[0]]
    if switch:
        answer = answer[::-1]

elif chai == 4:
    fronts = find_end(a, a_info[0], a_info[1], 'front')
    connects_1 = find_connect(a_info[0] - 1, a_info[0])
    line = find_end(_, a_info[0] - 1, _, 'line')
    connects_2 = find_connect(b_info[0], b_info[0] + 1)
    backs = find_end(b, b_info[0], b_info[1], 'back')
    ways_1 = {}
    for front in fronts.keys():
        for w in connects_1[front]:
            way = fronts[front][::-1] + [w]
            if w not in ways_1.keys() or len(way) < len(ways_1[w]):
                ways_1[w] = way
    for key in ways_1.keys():
        ways_1[key] += line[key][1:]
    ways_2 = {}
    for key, lst in ways_1.items():
        for w in connects_2[lst[-1]]:
            way = ways_1[key] + [w]
            if w not in ways_2.keys() or len(way) < len(ways_2[w]):
                ways_2[w] = way
    answer = []
    for back in backs.keys():
        ans = ways_2[back] + backs[back][1:]
        if not answer or len(ans) < len(answer):
            answer = ans
    if switch:
        answer = answer[::-1]

elif chai == 5:
    fronts = find_end(a, a_info[0], a_info[1], 'front')
    backs = find_end(b, b_info[0], b_info[1], 'back')
    connects = find_connect(b_info[0], a_info[0])
    ways = {}
    for front in fronts.keys():
        for w in connects[front]:
            way = fronts[front][::-1] + [w]
            if w not in ways.keys() or len(way) < len(ways[w]):
                ways[w] = way
    answer = []
    for back in backs.keys():
        ans = ways[back] + backs[back][1:]
        if not answer or len(ans) < len(answer):
            answer = ans
    if switch:
        answer = answer[::-1]

print(*answer)