Algorithm/Simulation

[백준 14500번] 테트로미노 (C/C++)

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 테트로미노 문제는 종이의 각 좌표에 대칭/회전시킨 각각의 테트로미노를 놓아봄으로써 문제를 해결할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; #define x first #define y second int n, m; int board[500][500]; typedef struct { vector pos; // 테트로미노를 구성하는 좌표 int n,..

[백준 3190번] 뱀 (C/C++)

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 뱀의 이동 규칙에 따라 코드를 작성하면 문제를 해결할 수 있습니다. 뱀의 몸 길이를 늘려 방향에 따라 한 칸 이동한다. 벽 또는 자기 자신과 부딪혔는지 확인한다. 부딪혔다면 게임을 종료한다. 이동하는 칸에 사과가 있는지 확인한다. 있다면, 칸에 있던 사과를 제거한다. 없다면, 꼬리가 위치한 칸을 비워준다. 방향을 변환할 시간이라면, 방향을 변환해준다. 전체 코드는 아래와 같습니다. #include usi..

[백준 14503번] 로봇 청소기 (C/C++)

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 로봇 청소기 문제는, 청소기의 동작 방식을 그대로 코드에 작성해주시면 됩니다. 문제에서는 북, 동, 남, 서를 0, 1, 2, 3으로 제시했지만, 왼쪽 방향이 증가하는 순서가 되도록 바꿔주고, Mod 연산을 사용하였습니다. 아래는 전체 코드입니다. #include using namespace std; typedef struct { int x, y, dir; }state; int board[50]..

[백준 16985번] Maaaaaaaaaze (C/C++)

https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net Maaaaaaaaaze는 판의 회전과 쌓는 순서를 계산하기 위해 백트래킹을 사용하였고, 미로를 탈출하기 위한 이동 횟수를 계산하기 위해 BFS를 사용하였습니다. 전체 코드는 아래와 같습니다. #include using namespace std; typedef struct{ int z, x, y; }pos; int dx[6] = {-1, 0, 0, 1, 0, 0}; int dy..

[백준 14499번] 주사위 굴리기 (C/C++)

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 주사위를 굴리면 굴리는 방향의 숫자가 원형 큐처럼 돌아가고, 다른 방향의 숫자는 영향을 받지 않습니다. 예를 들어 전개도가 아래와 같을 때, 오른쪽으로 주사위를 굴리면, 4, 1, 3, 6이 원형 큐처럼 돌아갑니다. 위쪽으로 굴리면, 2, 1, 5, 6이 원형 큐 처럼 돌아갑니다. 2 4 1 3 5 6 따라서 전개도의 4, 1, 3..

[백준 11559번] Puyo Puyo (C/C++)

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net Puyo Puyo 문제는 BFS와 큐를 이용하여 해결했습니다. 아래는 전체 코드입니다. #include using namespace std; #define x first #define y second char board[12][6]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int ans = 0; void drop()..

[백준 15686번] 치킨 배달 (C/C++)

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨 배달 문제는 next_permutation()을 이용하여 조합(Combination)을 구하고, 각각의 경우의 수에 대해 치킨 거리를 계산하여 해결했습니다. 아래는 전체 코드입니다. #include using namespace std; #define x first #define y second int n, m; int board[50][50]; int dist(vecto..

[백준 12100번] 2048 (easy) (C/C++)

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048 문제는 백트래킹을 이용하여 이동의 모든 경우의 수를 구하고, 큐를 이용하여 각 경우의 수에 대해 가장 큰 블록을 계산하였습니다. 아래는 전체 코드입니다. #include using namespace std; #define x first #define y second int board[20][20]; vector p; vector selected(5); int ..