목록백트레킹 (12)
어흥
문제 링크: www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net 1. 주의할 점 - EOF를 입력 받을때까지 수행한다 - 매 TC마다 초기화를 진행한다 - 백트레킹으로 진행하므로 사용을 다 했다면, True->False로 꼭 바꿔준다 2. 구현 - Cin>>row>>col을 통해 EOF를 입력 받을때까지 수행한다 - Arr[][]배열을 입력받으면서 Check[][] 배열을 초기화한다 - 만약 공을 놓을 수 있는 자리라면, 해당 자리의 Check[][]..
문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 두 일꾼이 같은 선택된 벌꿀통을 고르면 안된다 - 각 칸을 기준으로 최대 M칸까지 오른쪽으로 골랐을때의 최대 가중치를 저장한다 2. 구현 - Check[][] 배열을 false로 초기화시켜서 같은 벌꿀통을 고르지 않도록 확인하기 위해 false로 전부 초기화한다 - DFS() 사용하여 해당 칸을 골랐을 때 기준으로 최대값을 (가중치의 내림차순 순서로 정의)우선순위큐에..
문제 링크: https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위�� www.acmicpc.net 1. 주의할 점 - 플로이드와샬 알고리즘을 통해 미리 각 Node간 최단거리를 구해놓는다 2. 구현 - 각 Node간의 거리를 입력 받은 후, 플로이드 와샬 알고리즘을 사용하여 각 Node간 최단거리를 구한다 - 시작하는 행성의 Visit[]값을 True로 바꾼후, DFS()를 수행한다 - DFS(int idx, int dist, int planet) 함수는 각각 현재 행성,..
문제 링크: https://www.acmicpc.net/problem/3671 3671번: 산업 스파이의 편지 문제 안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요. 저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매�� www.acmicpc.net 1. 주의할 점 - 소수인 수를 미리 구해놓는다 - 매 TC마다 벡터들을 초기화한다 2. 구현 - 에라토스테네스의 체를 이용하여 소수면 Num[] 배열 자기자신을 입력한다 - 1~입력받은 수의 자리수 까지 DFS를 수행하며 구한 수가 소수라면 Set에 넣는다 #define MAX 10000000 #include #include #include #include #include #i..
문제 링크: https://www.acmicpc.net/problem/3967 3967번: 매직 스타 문제 매직 스타는 1부터 12까지 숫자가 헥사그램(hexagram)에 채워져 있는 모양으로 이루어져 있다. 매직 스타의 이름에 매직이 들어가는 이유는 숫자 네 개로 이루어진 줄의 숫자를 모두 합하면 26� www.acmicpc.net 1. 주의할 점 - 마지막에 모든 경로의 합을 구하면 TLE 발생한다. 특정 지점마다 검사해줘야 한다 2. 구현 - Check[] 배열을 전부 -1로 초기화한다 - Check[] 배열을 통해 해당 번호가 현재 사용중이라고 표시한다 - Test[][] 배열을 통해 어떤 경로에 위치한 숫자를 계산해야 하는지 표시한다 - DFS()를 수행하며 Idx가 5,8,11,12일때 특정 ..
문제 링크: https://www.acmicpc.net/problem/2549 2549번: 루빅의 사각형 첫 번째 줄에는 움직이는 횟수를, 두 번째 줄부터는 한 줄에 하나씩 타일을 움직이는 방법을 순서대로 출력한다. 이때, 격자판의 i번째 행을 k칸 움직였다면 정수 1과 i와 k를 빈칸을 사이에 두고 www.acmicpc.net 1. 주의할 점 - 푸는 방법이 여러가지 존재하지만, 여기서는 백트레킹을 활용해서 해결한다 - 한 열/행을 1~3칸 이동하는것은 전부 1번 옮긴것과 같다 2. 구현 - 현재 배열의 상태(Arr[][])와 최종적으로 원하는 배열의 상태(Corr[][])를 비교하여 틀린 개수를 반환하는 Cal() 함수를 구현한다 - Cal() 함수를 통해 다른 개수를 반환 받은 후, 다음과 같은 가..
문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 2가지의 조건을 통해 TLE를 예방한다 1) 저울에 올릴 때, 오른쪽의 총합 > 왼쪽의 총합이 된다면 무조건 왼쪽에만 추가한다 2) 남은 저울을 모두 오른쪽에 올려도 오른쪽의 총합
문제 링크: https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작�� www.acmicpc.net 1. 주의할 점 - 전부 S를 입력했을 때, 3546이 나와야 한다 - 이다솜파인 학생이 4명 이상 있어야 한다 2. 구현 - DFS와 백트레킹을 통해 구현한다 - DFS(idx,lee,lim) 함수를 통해 각 학생들을 V 벡터에 저장하고, Lee>Lim인 경우에만 V 벡터에 저장된 학생들이 모두 붙어있는지 확인한다 - Check_near() 함수를 통해 각 벡터들이 서로 인접해 있는..