반갑습니다!

16197번: 두 동전 www.acmicpc.net 풀이 시뮬레이션 문제이다. BFS를 통해 모든 경우를 탐색하여 해결하였다. 이 때, 동전이 2개이므로 중복 체크를 위한 배열을 visited[cy1][cx1][cy2][cx2]로 두었다. 코드 #include #include #include using namespace std; struct Coins { int x1, y1, x2, y2, cnt; }; int n, m, cx1, cy1, cx2, cy2; char map[20][20]; bool visited[20][20][20][20]; const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 }; bool inRange(int x, int y) { retur..

16985번: Maaaaaaaaaze www.acmicpc.net 풀이 구현이 까다로운 문제이다. 이 문제는 완전탐색으로 해결하였다. 이 문제는 크게 세가지의 구현을 해내면 풀 수 있다. 1. 5x5 크기의 판 쌓기 (Permutation) 2. 5x5 크기의 판 돌리기 3. 3차원 최단 경로 찾기 (BFS) 우선 5x5 크기의 판 쌓기는 순열을 사용해서 간단히 구현할 수 있다. 각 판의높이를 나타내는 숫자 배열 h = \[0, 1, 2, 3, 4\]가 있다고 하자. h 배열의 숫자를 정렬하는 방법은 [0, 1, 2, 3, 4]부터 [4, 3, 2, 1, 0]까지 총 120가지의 경우가 나온다. 따라서 이를 이용하면 판을 쌓는 모든 경우를 쉽게 구현할 수 있다. 이번엔 5x5 크기의 판 돌리기를 알아보자..

13460번: 구슬 탈출 2 www.acmicpc.net 풀이 BFS를 사용하여 해결할 수 있는 문제이다. 이 때 신경써야 할 좌표가 빨간공의 x, y좌표와 파란공의 x, y좌표로 총 4개이다. 따라서 중복체크를 위한 배열을 visited[red.y][red.x][blue.y][blue.x]로 4차원으로 선언하여 해결하였다. ## #include #include using namespace std; struct Ball { int x, y; }; int n, m; char map[10][11]; bool visited[10][10][10][10]; Ball red, blue; const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 }; int bfs() { qu..

1938번: 통나무 옮기기 www.acmicpc.net 풀이 BFS를 통해서 해결할 수 있는 문제이다. 나무가 놓일 수 있는 방법이 2가지이므로 중복체크를 위한 visited배열을 visited[50][50][2]로 선언하여 방향에 따라 체크해주었다. 그리고 나무의 중심부를 저장하여 회전할 수 있는지, 이동시킬 수 있는지 확인하였다. 코드 #include #include #include #include using namespace std; struct Tree { int x, y, dir, cnt; }; int n; char map[50][51]; bool visited[50][50][2]; vector tree, fin; const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0,..

2146번: 다리 만들기 www.acmicpc.net 풀이 까다로운 BFS 문제이다. 2번의 BFS를 통해 해결하였다. 섬들의 번호를 매긴다. 섬들의 거리를 구한다. 섬들의 번호를 매기는 경우는 한 육지에서 인접한 육지를 계속해서 탐색함으로써 쉽게 해결할 수 있다. 섬들 간의 거리를 구하는 것은 한 육지에서 인접한 바다를 탐색하며 다른 번호의 육지가 나올 때까지 탐색하면 된다. 코드 #include #include #include using namespace std; int n, ans = 987654321; int map[101][101]; bool visited[101][101]; vector p; const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };..