컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 문제 해결 알고리즘 BFS문제이지만 불을 피해서 탈출을 해야하므로 우선 큐에 불을 모..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 해결 알고리즘 그냥 bfs 한 번 해준 값과 적색과 녹색을 한가지의 색으로 바꾼 bfs값을 각각 출력한다. 소스 코드 #include using namespace std; int N; char arr[101][101]; int visited[101][101]; int cnt = 0; int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; bool ..

분기한정법이란? 분기한정 설계전략은 상태공간트리를 사용해 문제를 푼다는 사실이 되추적과 매우 비슷하다. 차이점으로 분기한정법은 (1) 트리 횡단방법에 구애받지 않고, (2) 최적화 문제를 푸는데만 쓰인다. 분기한정 알고리즘은 어떤 마디가 유망한지를 결정하기 위해서 그 마디에서 수(한계값)를 계산한다. 이 수는 그 마디 아래로 확장해 구할 수 있는 해답의 한계(bound)를 나타낸다. 그 한계값이 그때까지 찾은 최고 해답값보다 더 좋지 않으면 그 마디는 유망하지 않다. 최적값은 문제에 따라서 최대값이 될 수도 있고, 최소값이 될 수도 있으므로 여기서 "좋다"란 문제에 따라서 더 작다는 의미도 되고 더 크다는 의미도 된다. https://kimmessi.tistory.com/74?category=871925..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 해결 알고리즘 위의 문제대로 3가지로 방식대로 bfs를 해주는데 이 때, visited배열을 선언해주어서 만약 방문한 수가 visited배열에서 true값을 나타내면 그 수의 탐색을 하지 않는 식으로하면 시간 초과를 피할 수 있다. 소스 코드 #include using namespace std; bool visited[1000001]; typedef struct CT{ vector v; int result; }ct; void bfs(int N){ vector v; v.push_back(N); qu..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 해결 알고리즘 전형적인 BFS문제였다. 하지만 visited 배열을 써서 필요 없는 너비 탐색 시간을 아끼고 L,R연산할 때 int를 string으로 변환하지 말고 바로 수식을 써서 결과를 내 메모리를 아끼는 방향으로 하는 문제였다. 소스 코드 #include using namespace std; int A, B; bool visited[10001]; string bfs(){ q..

www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제 해결 알고리즘 이 문제는 전형적인 BFS 문제였다. 1. 모든 입력(배열의 크기(n), 시작점(cur_x, cur_y), 도착점(arr_x, arr_y)를 전부 입력 받은 후, 너비 우선 탐색 함수에 모두 입력으로 넣는다. 2. 전형적인 bfs대로 함수를 구성해주면 된다. 큐에 새로운 원소를 집어 넣을 때는, 배열 밖으로 말이 나갔는지 이동했던 좌표인지 확인해주고 다음에 갈 좌표에 해당하는 배열 원소에는 전..

www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 해결 알고리즘 이 문제는 3차월 배열을 사용하고 구조체를 사용하는 것 정도가 까다롭고 나머지는 전형적인 BFS 방식으로 푼 문제인 것 같다. 1. 우선 3차원 배열(arr), x,y,z에 입력을 각각 받는다 이때, 좌표에서 1인 부분이 토마토가 있는데 그 부분을 전부 큐에 집어 넣는다. (3차원 좌표를 넣을 구조체가 들어갈 큐이다.) 2. bfs 함수를 설계한다. 전형적인 bfs 과..

www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제 해결 알고리즘 1. 시작점을 입력 받고 편의점에 해당하는 좌표와 끝점을 벡터(v)에 전부 입력 받는다. 2. 전형적인 bfs 함수대로 하는데 이때 end_x, end_y 와 x, y 가 같으면 그때 happy를 출력해주고 함수를 종료해준다. 3. 만약 같지 않다면, 벡터(v)에 저장되어있는 편의점 좌표와 큐의 처음있는 좌표와의 거리를 구해서 1000이하이면 큐(q)에 넣어준 후 그 부분을 벡터에서 지..

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 해결 알고리즘 1. 우선 토마토의 배열을 배열(arr)에 전부 입력을 받는다. 2. 방문확인(visited) 배열에 익은 토마토 칸(1)과 토마토가 없는 칸(0)을 입력하고,익은 토마토의 좌표를 큐(q)에 차례대로 저장한다. 3. 큐(q)에 저장한 익은 토마토의 좌표들을 차례대로 동서남북 방향으로 일수마다 한 칸씩 전진하면서 전에 있던 칸의 숫자에 +1 한 값을 입력한다. 그 과정에서 방문..

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 문제 해결 알고리즘 1. 물고기 배열(arr)에 모든 입력을 받은 후, 큐(q)에 물고기가 있는 위치를 전부 저장한다. 2. 큐에 있는 위치들을 차례로 방문 확인 배열(visited)에서 탐색(bfs)한 후, 각 위치마다 가장 가까운 물고기와의 거리를 기록한다. 3. 탐색을 다 끝낸후, 물고기 방문 확인 배열(visited)에서 위치 중 가장 큰 숫자를 찾아서 출력(r..