디버깅

https://www.codetree.ai/training-field/frequent-problems/problems/debugging/description?page=1&pageSize=20 

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

스스로 어떻게 이렇게 엣지케이스를 못잡는지 신기할 정도입니다. 진짜 개발자에 재능이없는건가....

 

1.  실패 -> n이 x축, h가 y축인데 둘을 헷갈려서 index가 터졌습니다.

n -> h로 변경

import copy
from itertools import combinations


n, m, h = map(int, input().split())
lostLines = [ list(map(int, input().split())) for _ in range(m) ]
answer = -1
def start(locations, graph):
    global n
    y, x = locations

    while y != n:
        y += 1
        if graph[y][x] == "R":
            x += 1
        elif graph[y][x] == "L":
            x -= 1
    return x

def test(graph):
    starters = [[-1,i] for i in range(n)]
    for i in range(n):
        arrive = start(starters[i], graph)
        if arrive != i:
            return False
    return True

def validation(y, x, graph):
    global n
    left = False
    right = False
    if x - 1 < 0 or (graph[y][x - 1] != "L" and graph[y][x - 1] != "R"):
        left = True
    if x + 1 >= n or (graph[y][x + 1] != "L" and graph[y][x + 1] != "R"):
        right = True
    return left and right

def install_newLine(c):
    global n, graph, h, answer
    if answer != -1:
        return
    for i in combinations([i for i in range(n - 1)], c):
        tmp_graph = copy.deepcopy(graph)
        for x in i:
            for y in range(h):
                if validation(y, x, tmp_graph):
                    tmp_graph[y][x], tmp_graph[y][x + 1] = "R", "L"
                    break
        if test(tmp_graph):
            answer = c
            return


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

for y, x in lostLines:
    graph[y - 1][x - 1] = "R"
    graph[y - 1][x] = "L"


for c in range(1, 3 + 1):
    install_newLine(c)

print(answer)

 

 

2,3,4 실패 -> 한 y축에는 한번의 경로만 그어도 된다고 생각한 것부터가 실수였습니다. 결국 combinations 를 통해 케이스 전부를 검수하도록 변경하였습니다.

import copy
from itertools import combinations


n, m, h = map(int, input().split())
lostLines = [ list(map(int, input().split())) for _ in range(m) ]
answer = -1
def start(locations, graph):
    global h
    y, x = locations

    while y != h:
        if graph[y][x] == "R":
            x += 1
        elif graph[y][x] == "L":
            x -= 1
        y += 1
    return x

def test(graph):
    starters = [[0,i] for i in range(n)]
    for i in range(n):
        arrive = start(starters[i], graph)
        if arrive != i:
            return False
    return True

def validation(y, x, graph):
    global n
    left = False
    right = False
    if x - 1 < 0 or (graph[y][x - 1] != "L" and graph[y][x - 1] != "R"):
        left = True
    if x + 1 >= n or (graph[y][x + 1] != "L" and graph[y][x + 1] != "R"):
        right = True
    return left and right

def install_newLine(c):
    global n, graph, h, answer
    if answer != -1:
        return
    for i in combinations([i for i in range(n - 1)], c):
        tmp_graph = copy.deepcopy(graph)

        for x in i:
            installed = True
            for y in range(h):
                if installed and validation(y, x, tmp_graph):
                    tmp_graph[y][x], tmp_graph[y][x + 1] = "R", "L"
                    installed = False
        if test(tmp_graph):
            answer = c
            return




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

for y, x in lostLines:
    graph[y - 1][x - 1] = "R"
    graph[y - 1][x] = "L"

if test(graph):
    answer = 0
for c in range(1, 3 + 1):
    install_newLine(c)

print(answer)

 

5. 성공

import copy
from itertools import combinations

n, m, h = map(int, input().split())
lostLines = [ list(map(int, input().split())) for _ in range(m) ]
answer = -1
def start(locations, graph):
    global h
    y, x = locations

    while y != h:
        if graph[y][x] == "R":
            x += 1
        elif graph[y][x] == "L":
            x -= 1
        y += 1
    return x

def test(graph):
    starters = [[0,i] for i in range(n)]
    for i in range(n):
        arrive = start(starters[i], graph)
        if arrive != i:
            return False
    return True

def validation(y, x, graph):
    global n
    left = False
    right = False
    if x - 1 < 0 or (graph[y][x - 1] != "L" and graph[y][x - 1] != "R"):
        left = True
    if x + 1 >= n or (graph[y][x + 1] != "L" and graph[y][x + 1] != "R"):
        right = True
    return left and right

def install_newLine(c):
    global n, graph, h, answer
    if answer != -1:
        return
    newLinelocation = []
    for ty in range(h):
        for tx in range(n - 1):
            newLinelocation.append([ty, tx])
    for i in combinations(newLinelocation, c):
        tmp_graph = copy.deepcopy(graph)

        for y, x in i:
            if validation(y, x, tmp_graph):
                tmp_graph[y][x], tmp_graph[y][x + 1] = "R", "L"
                if test(tmp_graph):
                    answer = c
                    return

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

for y, x in lostLines:
    graph[y - 1][x - 1] = "R"
    graph[y - 1][x] = "L"

if test(graph):
    answer = 0
for c in range(1, 3 + 1):
    install_newLine(c)

print(answer)