본문 바로가기

Backtracking6

[백준] 2580.스도쿠 / BackTracking @BackTracking / 1h 4m 40분만에 풀었는데 시간초과 떠서 그거 잡느라 좀 오래 걸림 문제 링크 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 구현 포인트 원래 check라는 함수를 두고 모든 칸을 다 채운 후 가로줄, 세로줄, 3*3칸에 중복되는 숫자가 없을 때에만 맵을 출력하고 종료하게 했다. 그런데 이 중복체크를 안 해도 풀린다! 1. 3차원 visit 사용하기 visit[행][열][1부터 9까지의 값] 으로 그 칸에 들어.. 2020. 9. 8.
[백준] 9663.N-Queen / BackTracking @BackTracking / 1h 나이트랑 헷갈려서 바보짓 하고.. 이후에 이전 코드 보고 다시 풀었음 ㅜㅜ 문제 링크 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 참고 자료 퀸의 공격 범위 : 수직, 수평선 및 대각선 4방향 즉, 아래에서 검은색으로 표시된 칸에는 다른 퀸을 놓을 수 없다. 출처 : http://blog.daum.net/tomayoon/7089880 구현 포인트 처음에 visit 표시를 어떻게 하지 고민이 많았다 만약 단순히 backTra.. 2020. 9. 6.
[백준] 10971.외판원 순회 2 @BackTracking / 28m (생각, 필기 20분) 알고리즘 쉰지 너무 오래돼서.. 이거 뭘로 풀어야하지 크루스칼인가.. 멍때리다가 생각하다가 떠올림 문제 링크 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 방법 1. 시작점으로 다시 돌아와야 한다 -> 즉, 어떤 점에서 출발하든 상관 없다 라는 의미임 예를 들면 1->2->3->4->1로 가는 경로라면, 2->3->4->1->2도 같은.. 2020. 9. 6.
[백준] 17779.게리맨더링2 (java) / BackTracking, DFS, 시뮬레이션, 완전탐색 @BackTracking, DFS, 시뮬레이션, 완전탐색 / 4h 이상 (디버깅만 3시간 한 듯) SWEA 2105.디저트 카페 ( 포스팅 ) 와 비슷한 문제처럼 보여서 쉽겠거니 하고 풀었는데, 테케조차 계속 틀리게 나와서 디버깅하느라 너무 힘들었다..ㅠ 풀고나서 다시 보니 너무 어렵게 생각했던 것 같다. 그래도 백트래킹 공부하기에는 좋은 문제인 듯.. 문제 링크 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정.. 2020. 3. 8.
[백준] 14502.연구소 (java) / 백트래킹, DFS, BFS, 조합 @백트래킹, DFS, BFS, 조합 / 29m (필기 15m 포함) 기본 문제라서 무난하게 풀었다. 문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 구현 방법 이 문제는 빈 칸.. 2020. 2. 25.

티스토리툴바