글 읽기 - 15566 질문입니다.

dlwhdgh98 1년 전 0

잘 짠거같은데 어디가 틀렸을까요..?

푼 방식은

1. 개구리들의 선호 연꽃으로 재귀함수를 돌리면서 순열을 만든다.

2. 만약 순열의 길이가 n개가 되면 check함수를 이용해서 입력받은 m개의 정보들로 개구리들의 주제가 같은지 확인한다

3. 맞으면 YES출력 후 포지션을 출력. 아니면 계속 재귀함수 돌리다가 다 끝나도 못찾으면 NO를 출력한다.

# 통나무 정보가 잘 맞는지 체크하는 함수
def check(frogs):
    for i in range(m):
        a, b, t = tree[i]
        # 서로의 주제 흥미도가 다르면 잘못자리잡음
        if frog[frogs[a-1]-1][t-1] != frog[frogs[b-1]-1][t-1]:
            return False
    return True

def find_pos(cur_pos, num):
    if num == n:
        # 자리를 맞게 잡았으면 출력 후 종료.
        if check(cur_pos):
            print("YES")
            print(*cur_pos)
            exit()
        return

    for i in p[num]:
        if i not in cur_pos:
            find_pos(cur_pos + [i], num+1)

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

# 개구리들의 각 주제 흥미도
frog = [list(map(int, input().split())) for _ in range(n)]

# 개구리들의 선호하는 연꽃리스트
p = []

for i in range(1, n+1):
    a, b = map(int, input().split())
    if a == b: # 같으면 1개이므로 a나 b 아무거나 넣는다.
        p.append([a])
    else:
        p.append([a, b])

# 통나무 정보        
tree = [list(map(int, input().split())) for _ in range(m)]

num = 0 # 현재 개구리 번호
find_pos([], 0)
# 함수를 나왔다는건 못찾았다는 의미.
print("NO")

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

15566 질문입니다.

dlwhdgh98 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말