Baekjoon Review

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제는 BFS를 통해 해결할 수 있다. 100칸의 배열을 생성하고 뱀과 사다리와 무관하게 index, value를 통해 배열에 요소를 집어 넣는다. queue의 값이 100이 되면 반복을 멈추고 이동 횟수를 저장한다. 주사위는 1~6까지 있고, 최대 값은 100까지이므로 조건문으로 제어한다. 뱀과 사다리가 있다면 뱀과 사다리 값을 queue에 삽입..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 BFS를 사용해서 해결할 수 있다. 현재 queue에 있는 값이 1이면 연산 횟수를 저장하고 반복을 멈춘다. 값이 3으로 나눠 떨어지거나 2로 나눠 떨어지면 queue에 값을 3이나 2로 나누고 연산 횟수를 저장한다. 또한 값을 1로 뺀 값과 연산 횟수를 저장한다. #include #include #include #include using namespace std; int x, result; queue q; void bfs() { q.push(make_pair(x,0)); while (!q.empty..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제는 BFS를 통해 해결할 수 있다. 탐색을 통해 원하는 좌표에 이동하면, 배열에 이동 값을 삽입한다. 이후 배열을 정렬하여 최소 값을 출력하면 된다. #include #include #include #include using namespace std; int visited[101][101]; int N, M; char graph[101][101]; int dx[] = { 0,0,-1,1 }; int dy[] = { -1,..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이 문제는 DFS를 사용하고, 영역 검사를 하면 해결할 수 있다. #include #include #include #include using namespace std; int visited[26][26]; int dx[] = { 0,0,-1,1 }; int dy[] = { -1,1,0,0 }; vector v; int N, counter = 0, cnt=0; char graph[26][26]; vo..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B) conti..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 이 문제는 DFS를 통해 해결할 수 있다. 알고리즘은 다음과 같다. 색약이 아닌 경우 배열을 순회하고 방문하지 않은 경우 인자로 들어온 x, y의 색과 상, 하, 좌, 우내의 색이 같은 경우 즉, R G B인 경우 탐색을 하여 색의 범위를 찾는다. 색의 범위를 찾았다면 count를 증가시킨다. 색약인 경우 먼저 Graph에 있는 G를 R로 바꾼 후 색약이 아닌 경우와 동일하게 탐색을 진행한..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이 문제는 7576번 토마토와 유사한 문제이다. 하지만 이 문제는 x, y 뿐만 아니라 z 방향이 추가된 문제이다. 따라서 익은 토마토를 계산하기 위해 앞, 뒤도 추가해서 검사해야한다. 이를 위해 dz라는 배열을 선언하였다. 이동 가능한 범위를 검사하고 방문하지 않은 위치이면 토마토를 익히고 큐에 경로를 삽입한다. #include #include using namespace..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 이 문제는 BFS를 사용하면 해결할 수 있다. 이 문제에서 가장 어려웠던점은 메모리 관리였다. 처음에 queue와 방문 확인을 위한 행렬을 전역 변수로 생성하였다. 이러한 접근은 메모리 초과라는 오류를 발생시켰다. 따라서 bfs 함수 내에서 queue를 할당하고 함수가 끝나면 queue를 소멸하게 하여 메모리 초과를 막을 수 있었다. 주요 알고리즘은 다음과 같다. 1. 입력 숫자 A와..