알고리즘
[이것이 파이썬 코딩테스트다 - 구현] 기둥과 보 설치
김치말이삼겹살
2024. 4. 11. 14:36
https://school.programmers.co.kr/learn/courses/30/lessons/60061
import copy
def check_fidelity(graph,x,y, a):
result = True
# 그래프 복사
new_graph = copy.deepcopy(graph)
# 그래프 해당 위치 삭제
new_graph[x][y][a] = -1
# print(new_graph[x][y][a])
# 그래프 탐색하며 모든 보와 기둥 이상 있는지 체크
n = len(new_graph)
for i in range(n):
for j in range(n):
# 기둥 이상여부 체크
if new_graph[i][j][0] == 1:
# 바닥 위에 있는지, 보의 한쪽 끝 부분 위에 있는지, 다른 기둥 위에 있는지 체크
if i == 1 or graph[i-1][j][0] == 1:
continue
elif x-1>=0 and graph[x-1][y][1] == 1:
continue
elif x-1 >=0 and y < n and graph[x-1][y+1][1] == 1:
continue
else:
result = False
break
if new_graph[i][j][1] == 1:
if graph[i][j-1][0] == 1 or graph[i][j][0] == 1:
continue
elif j < n:
if graph[i][j-1][1] == 1 and graph[i][j+1][1] == 1:
continue
else:
result = False
break
return result
def solution(n, build_frame):
answer = []
# graph 선언
graph = [[[-1,-1]] * (n+1) for _ in range(n+1)]
# print(graph)
# print(graph[0][0][0])
for bf in build_frame:
x, y, a, b = bf
# print(x,y,a,b)
# 성립 요건 부터 확인
if x < 0 and x > n and y < 0 and y > n:
continue
# 기둥인지 보인지 부터 확인
if a == 0:
# 삽입인지 삭제인지 여부 확인
# if x == 0:
# continue
if b == 0: # 삭제
# 남은 모든 보와 기둥이 문제가 없는지 확인 -> 함수로 만드는 게 나을지도
check = check_fidelity(graph, x,y, a)
# print(check)
if check == True:
graph[x][y][0] = -1
else:
continue
else: # 삽입
# 기둥 삽입 조건 확인
if x == 1 or graph[x-1][y][0] == 1:
graph[x][y][0] = 1
elif x-1>=0 and graph[x-1][y][1] == 1:
graph[x][y][0] = 1
elif x-1 >=0 and y < n and graph[x-1][y+1][1] == 1:
graph[x][y][0] = 1
else:
continue
elif a == 1:
# 삽입인지 삭제인지 여부 확인
# if y == 0: # 교차점이 끝
# continue
if b == 0: # 삭제
# 남은 모든 보와 기둥이 문제가 없는지 확인 -> 함수로 만드는 게 나을지도
check = check_fidelity(graph, x,y, a)
if check == True:
graph[x][y][1] = -1
else:
continue
else: # 삽입
# 보 삽입 조건 확인
if graph[x][y-1][0] == 1 or graph[x][y][0] == 1:
graph[x][y][1] = 1
elif y < n:
if graph[x][y-1][1] == 1 and graph[x][y+1][1] == 1:
graph[x][y][1] = 1
else:
continue
# graph 순회하면서 answer 입력받기
for i in range(n+1):
for j in range(n+1):
if graph[i][j][0] == 1:
answer.append([i,j,0])
elif graph[i][j][1] == 1:
answer.append([i,j,1])
return answer
흑흑,,, 풀려고 해도 대가리가 안돌아가네용,,,
나동빈씨 풀이 보면서 머가 문제인지 익혀야겠음
1. 자료구조
와 미친 이사람은 n*n 구조물 안 쓴다... 그냥 인덱스로 때려버리네...
2. 시작 점 -> 아 선생님,, 저 화날라고 그럽니다,,, 예ㅖㅖ???? x가 열이고, y가 행이네,,, ㅠㅠㅠ 엉엉 웁니다,,,
-> 문제 요구사항 제대로 읽기 !!!!
나동빈 씨 알고리즘은 대체적으로 각 판단을 요구하는 것 같다.
무슨 말이냐...
내가 이걸 2차원 리스트로 만들어야 하는지? -> 그렇지 않고 더 간단하게 푸는 방법은 무엇이 있을지?
주어진 제약 사항 안에서 더 빨리 풀 수 있는 방법이 있는지? -> 시간복잡도 각 재고 가장 나이브하게 풀 수 있는 방법은 무엇인지?
여기서 가장 간단하게 푸는 방법은...
일단 작동하는대로 넣거나 빼고, 모든 경우에 대해 탐색을 해서 가능하면 유지, 아니면 원상복구.
def possible(answer):
result = True
for x, y, a in answer:
# 기둥인 경우 가능한지
if a == 0:
if y == 0 or [x-1,y,1] in answer or [x,y, 1] in answer or [x,y-1,0] in answer:
continue
else:
result = False
break
# 보인 경우 가능한지
if a == 1:
if [x,y-1,0] in answer or [x+1,y-1,0] in answer or ([x-1,y,1] in answer and [x+1,y,1] in answer):
continue
else:
result = False
break
return result
def solution(n, build_frame):
answer = []
# 우선 입력 받는다.
for build in build_frame:
x, y, a, operation= build
if operation == 0:
# 리스트 지우는 method : remove
answer.remove([x,y,a])
if not possible(answer):
answer.append([x, y, a])
if operation == 1:
answer.append([x,y,a])
if not possible(answer):
answer.remove([x,y,a])
return sorted(answer)
반응형