깊이우선탐색2 [자바] 백준 23817 - 포항항 (boj java) 문제 : boj23817 상당히 좋은 아이디어 문제라 생각한다. 얼핏 브루트포스 문제로 생각하기 힘들고, 당연히 bfs로 어떻게든 잘 해야 할 것 같이 생겼다. 하지만 잘 생각해보면 단순 탐색으로는 최소시간을 찾기 힘들고 모든 경우의 수를 보는 brute force(완전탐색)로 봐야할 것임을 알 수 있다. 로직을 나눠서 생각해보자. 1. 최대 20개의 식당에 대해 5개의 식당을 방문하는데 필요한 최소한의 시간을 구할 수 있어야 한다. 이걸 확인하려면 기본적으로 방문 순서도 중요하다. 즉 20C5가 아니라 20P5로 봐야 한다. -> 모든 정점 사이의 거리를 안다면 1000x1000 짜리 배열이 아니라 최대 21개(S가 1개, K개 20개)의 정점과 그 사이에 거리에 관한 간선이 있는 그래프로 변경할 수 .. 2022. 6. 25. [자바] 백준 6755 - Who is taller? (boj java) 문제 : boj6755 입력으로 들어온 M개의 x가 y보다 크다는 정보를 가지고, p가 q보다 큰지(yes) 혹은 q가 p보다 큰지(no) 혹은 검증이 불가한지(unknown) 알아낼 수 있어야 한다. 그래프로 생각해보자. 우선 각 N명의 사람을 정점으로 하고, 간선을 x에서 y로 (즉 큰 사람에서 작은사람쪽으로) 하는 방향 그래프를 생각해보자. 그럼 간단히 p에서 q로 간선을 타고 이동이 가능하다면 p가 q보다 큰게 된다. 반대로 q에서 p로 간선을 타고 이동이 가능하다면 q가 p보다 큰게 된다. 둘 다 불가했다면 검증이 불가하다. 지문의 'you always compare correctly'에 따라 사이클이 생긴다거나, p에서 q로도 갈 수 있고 q에서 p로도 갈 수 있는 상황은 그냥 문제가 틀린셈이.. 2022. 6. 25. 이전 1 다음
