전체 글 (88) 썸네일형 리스트형 정올 1681 <해밀턴 순환회로> www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 JUNGOL www.jungol.co.kr 정 올의 해밀턴 순환 회로이다. 이문제는 기본적으로 백트래킹 문제이기 때문에 최대 12개의 배달 지를 순열로 놓으면서 거리를 계산하는 문제이다. 그러나 나는 새롭게 접근하기 위해 다익스트라 알고리즘을 응용하면서 비트 연산자를 더해 BFS로 문제를 접근해보았다. dis 클래스는 next는 다음 좌표이고 d는 다음 좌표까지의 총 이동거리를 나타내고 f는 비트 연산자로 visit을 나타낸다고 보면 된다. 이렇게 총 3가지로 구성된다고 보면 된다. 모든 곳을 다 탐색하고 다시 1로 돌아온 경우이고 최소의 거리를 출력하기 때문에 답을 입력하고 return을.. 백준 2933 <미네랄> 조건이 많아서 처리해야 될 부분이 많은 시뮬레이션 문제였다. 문제의 단계는 왼,오 순서대로 그 위치에 가장 가까운 미네랄을 사라지게 하는 것. 제거한 위치를 중심으로 4 방형을 검사해 미네랄 이 있으면 그 부분이 떨어져 있는 것인지 확인! 떨어져 있다면 얼마나 내려갈 수 있는지 체크! 이 순서로 진행되는 것이다. 이 부분에서 내가 헷갈렸던 부분이 2번에서 왜 4방향으로 해야 하는가 였다. 위 , 오른쪽, 왼쪽 이렇게 해주면 된다고 생각했는데 예외인 부분이 있었다. 그림처럼 화살표 부분을 부수게 되면 아래의 미네랄 뭉치가 동 떨어져 자유 낙하하게 되는 것이다. 이러한 실수를 고쳐야 문제를 빨리 풀 수 있을 텐데 ㅠㅠ 문제에 수행되는 총 시간 복잡도는 부수는 횟수를 수행하는 게 최대 100*총 BFS를 하기.. 백준 17471 <게리맨더링> 2가지 선거구로 나누고 선거구가 연결되어있는지 확인하는 문제! 즉 부분집합을 구하고 각각의 선거구에서 BFS를 실행해서 연결되어 있는지 확인하는 것!! 반대로 생각을 하면 복잡하기도하고... 풀리지 않는 문제 ㅜㅜ 즉 문제를 많이 풀어봐야 한다. 선거구를 두 개로 나눈 것이다. 이 cal 부분은 선거구가 두 개로 나뉘어서 연결되어 있는지 확인하는 코드이다. 두 개가 연결되었다면 count는 2가 될 것이고 값을 비교해서 넣어주게 된다. 인접 리스트를 이용해서 다음 노드가 같은 팀인지 확인하게 되고 같은 팀이라면 큐에 넣고 BFS를 실해해 주는 것이다. 이렇게 총 3단계를 이용해서 문제를 해결할 수 있다. 이 방법이 생각이 어떻게 나냐? 하는 사람들은 문제를 많이 풀어보길 권한다. 전체 코드 더보기 imp.. 이전 1 ··· 19 20 21 22 23 24 25 ··· 30 다음
