평면 그래프 썸네일형 리스트형 BOJ)3136 평면도 문제: icpc.me/3136좌표평면에 주어진 순서대로 그림을 그릴 때 평면도 상에서 존재하는 모든 방의 개수를 출력하는 문제이다.평면 그래프에서 V-E+F=2 라는 공식이 성립한다는 점을 이용하여 문제를 해결할 수 있다.(V:정점의 수, E:간선의 수,F:평면의 수)구해야 하는게 평면의 수 이므로 평면의 수는 F=2-V+E로 구할 수 있다. 하지만 좌표 평면 전체도 하나의 평면으로 세므로 답은 1-V+E가 된다.이제 V의 수와 E의 수를 구해야 하는데 이는 set을 이용하여 세주면 편리하게 계산할 수 있다.이 때 주의해야 할 점이 대각선으로 만나는 점을 처리해주기 위해 한 방향으로 나아갈 때 두번씩 나아가도록 점을 찍어주어야 한다. 자세한 것은 소스를 보며 이해하도록 하자.1234567891011121.. 더보기 BOJ)11975 Build Gates 문제: icpc.me/11975 펜스를 동서남북으로 치려고 할 때 펜스로 인하여 닫힌 구간은 나가야 할 문이 필요하다고 할 때 문의 최소 개수를 출력하는 문제이다. 문제를 다시 해석하자면 그래프를 그린 뒤 완전히 닫혀있는 구간의 개수를 세는것이다. 즉 평면의 개수를 찾는 문제인데, 선을 그어서 생긴 그래프이므로 평면그래프가 되니 V-E+F=2라는 공식을 이용하여 F=2-V+E로 평면의 개수를 구할 수 있다. 이때 그래프 전체가 평면의 개수에 포함되기 때문에 F-1을 출력해주면 된다. Vertex와 Edge는 중복이 되면 안되므로 set을 통하여 관리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #i.. 더보기 이전 1 다음