corgi_muzi   3년 전

문제 입력의 조건 중 정점의 개수 N이 1 이상이라고 나와있는데 간선의 개수 M 역시 1 이상이라고 나와있습니다.

문제에서 간선의 개수(M)개의 줄에 걸쳐 간선이 연결하는 두개의 정점이라고 표현하고 있는데 N이 1이고 M이 1 이상일 경우 두개의 정점을 표현하지 못합니다.

N의 범위를 2 이상이 되도록 문제의 조건의 변경을 건의합니다.

hjroh0315   3년 전

기본적으로 자기 자신을 연결하는 간선도 간선이긴 합니다. 대부분의 문제에서는 이러한 경우가 없다고 규정하지만, 이러한 간선을 self loop라고 부르며, 이것 또한 엄연히 간선으로 봅니다.

djm03178   3년 전

설령 그런 간선을 허용하지 않는다고 해도 문제 없습니다. 원래 모든 조건을 만족하는 입력만 주어지는 것이므로 일부 조건의 전체 범위 내에 실제로는 주어지는 것이 불가능한 것들이 있을 수 있고 이는 문제가 되지 않습니다.

corgi_muzi   3년 전

djm03178님이 작성해주신 댓글을 이해하는데 조금 어려워 댓글을 남깁니다.

"원래 모든 조건을 만족하는 입력만 주어지는 것이므로 일부 조건의 전체 범위 내에 실제로는 주어지는 것이 불가능한 것들이 있을 수 있고" 의미가 뭔지 헷갈립니다.

[원래 모든 조건을 만족하는 입력만 주어진다] 는 이해했습니다. 다만 이 문제에서 표현하는 1개의 간선이 1개의 정점간 가지는것이 불가능하지 않나요? 라는 의문에 질문을 남겼었고, 1개의 정점만 순회하는 간선도 포함한다고 하여 문제를 다시 해석했을 때, 문제가 없음을 이해했습니다.

[일부 조건의 전체 범위 내에 실제로는 주어지는 것이 불가능하다] 가 헷갈립니다. 모든 조건을 만족하는 입력이라면 당연히 각각의 일부 조건도 만족할텐데 어떤 입력은 불가능하다는 것이 헷갈립니다. 

문제의 모든 입력 조건은 상호 관련성이 있기 때문에 1번 입력에 따라 2번 입력의 조건이 상이할 수 있고, 결과적으로 2번 입력 조건의 전체 범위는 만족하지만 1번 입력에 영향을 받아 변경된 2번 입력의 조건에는 만족하지 않을 수 있어 입력으로 주어지는 것이 불가능하다는 의미인가요?

마지막으로 문제 없다라는 표현이 문제를 이해하는데 어려움이 없다는 내용인지, 실제로 코드를 작성할 때 예외가 없다는 의미인지도 헷갈립니다.

pentagon03   3년 전

@corgi_muzi

Q: "원래 모든 조건을 만족하는 입력만 주어지는 것이므로 일부 조건의 전체 범위 내에 실제로는 주어지는 것이 불가능한 것들이 있을 수 있고" 의미가 뭔지 헷갈립니다.

A:  제한을 만족하는 모든 입력이 주어지지 않을 수 있다는 것입니다. 가령 1<=N,M<=100, N,M은 자연수인 조건을 가진 문제가 있다고 합시다. 이때 조건으로 명시되어 있지는 않지만, 문제 설명에 의해 N+M이 소수인 경우만 문제가 성립한다고 하면 (N,M) = (2,2) 등은 문제 조건을 만족하는 입력이지만 실제로 주어지는 것이 불가능합니다. 문제에서 일반적으로 "해가 존재하는 경우만 입력으로 주어진다", "문제를 구성할 수 있는 경우만 입력으로 주어진다" 등의 문장을 넣어주지만, 넣지 않는다고 하여 문제의 테스트케이스가 이 조건을 어긴 것은 아니기 때문에 테스트케이스 자체는 성립합니다. 단, 만약 이러한 경우, 문제의 설명이 불충분한 것은 맞다고 생각합니다. 문제를 푸는 사람 입장에서는 그러한 입력이 들어오지 않는 것을 확신할 수 없기 때문입니다.

Q: "마지막으로 문제 없다라는 표현이 문제를 이해하는데 어려움이 없다는 내용인지, 실제로 코드를 작성할 때 예외가 없다는 의미인지도 헷갈립니다."

A: 이 문제가 논리적으로 결함이 없다는 뜻입니다.

djm03178   3년 전

이 문제의 경우 만약 self loop가 없다는 조건이 있다면 N=1이 되면 다른 조건을 어기지 않고 테스트 케이스를 만드는 것이 아예 불가능하기 때문에 N=1인 경우가 입력에 존재하지 않는다고 확신할 수 있습니다.

corgi_muzi   3년 전

두분의 친절한 설명 감사합니다 ㅎㅎ

개인적으로는 존재하지 않을 입력에 대한 불필요한 정보를 제외하고 문제의 입력으로 들어오는 테스트 케이스들만을 만족하는 최소한의 범위만을 문제에 알려주는것이 옳다고 생각합니다만 현실적으로 어렵다고도 생각하기 때문에 말씀하신 내용이 뭘 의미하시는지 이해했습니다.

게다가 self loop를 몰랐던 제 무지함도 한몫 했네요... 알고 있었다면, djm0318님이 언급하신것처럼 self loop에 관한 조건이 있던 없던 문제가 없다고 생각했을텐데 말이죠..

문제와는 번외로 문제 출제 방식에 관심이 있어 질문 드립니다.

일반적으로 선이라는 것은 서로 다른 두 점이 연결되어있는 것이라고 이해하게 되는데, self loop와 같이 예외에 해당되는 부분은 별도로 언급하지 않는것이 일반적인건가요? 

아니면 self loop 역시 그래프 이론이므로 다른 자료 구조나 이론과 마찬가지로 문제를 해결하는데 요구하는 역량이라고 판단하여 일부러 언급하지 않았다고 봐야하나요?

문제에서는 구태여 서로 다른 두 점이 아닌 두 점이라고 표현한것으로 보아 self loop를 고려한 문제 출제였다고 생각이 되서.. 왜 해당 부분에 대해선 별도의 언급이 없었는지 의도가 궁금합니다.

djm03178   3년 전

일반적으로 서로 다른이라는 조건을 언급하지 않으면 self loop도 존재할 수 있음으로 보는 것이 맞기는 합니다. 물론 문제가 친절했다면 그런 간선도 있을 수 있음을 적어놓았겠지만, 안 적혀있으면 어쩔 수 없지만 푸는 사람의 몫입니다.

corgi_muzi   3년 전

감사합니다! 😉😉😉

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