개발기록 개발기록

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다. 게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에 www.acmicpc.net 완전 탐색 문제입니다. 백트래킹으로 순열을 구현하여 시뮬레이션 하면 됩니다. 윷놀이판의 저장 방법이나 윷놀이판의 순회 방법을 결..

https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다. 배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자. www.acmicpc.net 0을 하나하나 선택해서 1로 바꾸로 bfs를 돌린다면 매우 비효율적일 것 입니다. 처음에는 bfs를 돌리면서 1로 바꾸는 능력 사용여부를 확인해준다면 될 것이라고 생각했습니다. 실패했습니다. 그래서 모든 0에 대해 1로..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A에서 B로 가야합니다. dfs, bfs 탐색으로 중복을 제거해가며 탐색하기에는 시간이나 메모리가 부족합니다. 다른 방법이 필요합니다. 역으로 생각해봅시다. B에서 A로 가봅시다. A 에서 B로 올라가는 규칙에 의해서 중간 과정에 있는 수는 무조건 짝수이거나 마지막 자리수가 1인 수 밖에 없습니다. 그러므로 위 조건을 충족하면서 가다가 A가 되면 성공인 것이고 안되면 실패인 것이죠. 거꾸로 생각하기 #include #include #include #include using namespace std; int a, b; in..

https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다. www.acmicpc.net 완전 탐색 문제입니다. 거울을 설치할 수 있는 곳에 4가지 방법으로 설치 or 그냥 지나가기를 해줍니다. dfs, bfs 둘 다 가능한 방법이지만 저는 bfs로 하였습니다. bfs로 하면서 방문 체크를 해줘야합니다. 단순히 좌표로만 방문 체크를 해주면 방향처리가 안됩니다..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net https://www.acmicpc.net/problem/1260 문제에 대한 감이 아예 안오시면 이 문제를 완전히 이해해야 합니다. 기본적인 그래프 이론 문제입니다. 다리를 연결하는 방법을 전부 고려해야하는 완전 탐색 문제입니다. 우선 n개의 섬을 전부 연결하기 위해서는 최소 n-1개의 다리가 필요합니다. 즉, 다리 n-1개를 선택해야 합니다. 조합으로 선택하면 됩니다. 다..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 완전탐색 문제입니다. 정점을 선택한 후에 연결여부를 확인해야합니다. 선택은 백트래킹으로 하면 됩니다. 정점 선택은 조합으로 해야겠죠. 그럼 자연스레 2개의 그룹으로 나뉩니다. 확인은 bfs로 하면 됩니다. 2개의 그룹 모두 확인 해야합니다. 하나의 그룹이 모두 연결되어 있다고해도 다른 그룹은 아닐 수 있으니까요. #include #include #include using namespace std; const int I..

https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 r1, c1, r2, c2가 주어진다. 모두 절댓값이 5000보다 작거나 같은 정수이고, r2-r1은 0보다 크거나 같고, 49보다 작거나 같으며, c2-c1은 0보다 크거나 같고, 4보다 작거나 같다. www.acmicpc.net 구현 문제입니다. 메모리를 넉넉하게 사용할 수 있는 상황이라면 쉽게 구현할 수 있습니다. 한 껍데기에서 최저값 혹은 최대값을 기준으로 점진적으로 증가 혹은 감소를 하는 방법을 통해서 말이죠. 하지만 메모리가 부족한 상황입니다. 그래서 정확히 출력 범위에 대해서만 메모리를 사용해야 합니다. 그렇다면 결국엔 좌표를 통해서 값을 알아내야 합니다. 좌표 (y, x) n ..

https://www.acmicpc.net/problem/16939 16939번: 2×2×2 큐브 첫째 줄에 2×2×2 루빅스 큐브 각 면의 각 칸 색상이 주어진다. 색상은 1부터 6까지의 자연수로 나타내며, 각 자연수는 총 4번 등장한다. i번째 수가 의미하는 칸은 아래와 같다. www.acmicpc.net 시뮬레이션 문제입니다. 큐브를 한 번만 돌리면 되므로 12가지 경우의 수를 시뮬레이션 해야합니다. 마법같은 규칙을 발견할 수 없어서 하나하나 다 구현하였습니다. 상황 -> 동작 ) 상황 -> 동작 )-----> 모듈(매개변수) 상황 -> 동작 ) #include #include using namespace std; struct point { int z, y, x; }; int cube[6][2][2..