코딩하기 좋은날

https://www.acmicpc.net/problem/2178 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 배열에 1 과 0 을 입력받고 1로만 이동 하며 끝점까지 이동하는데 지나야하는 최소의 칸 수를 찾는 문제이므로 bfs를 이용해서 풀면 해결되는 간단한 문제입니다. 다음은 코드입니다. #include #include using namespace std; int N,M; int maze[101][101]; queue q; int nextx[4] = {1, 0, -1, 0}; int nexty[4] = {0, 1, 0, -1}; int visited[101][101]; int num = 1; void bfs() { q.push(make_pair(0, 0)); visited[0][0]..

https://www.acmicpc.net/problem/5014 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 엘리베이터를 이용해서 U층 만큼 위로 D층 만큼 아래로 갈 수 있는 버튼이 주어지고 현재층에서 목표층까지 최소의 버튼을 누르는 횟수를 구하는 문제입니다. bfs를 이용하여 목표층에 도달하는 최소 횟수를 구하면 됩니다. 위 아래 두가지로만 움직일 수 있고 1층 보다 아래로 갈 수 없고 최고층 보다 위로 갈수 없는 조건만 생각하면 특별함은 없는 문제입니다. 다음은 코드입니다. #include #include using namespace std; int F, S, G, U, D; //F는 총 건물의 높이 S에서 G층으로 이동 U만큼 위로 D만큼 아래로 이동가능 int num; boo..

https://www.acmicpc.net/problem/1012 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 배추밭에 배추가 심어져있는 좌표를 입력받은뒤 배추가 심어진 부분의 영역의 수를 구하는 문제입니다. 서로 인접해있는 영역은 하나의 배추벌레로 모두 보호가 되므로 main함수에서 dfs를 호출하는 횟수가 곧 필요한 배추벌레의 숫자입니다. 특별함은 없는 문제입니다. 다음은 코드입니다. #include using namespace std; int cabbage[51][51]; int nextx[4] = {1, 0, -1, 0}; int nexty[4] = {0, 1, 0, -1}; int M,N; void dfs(int a, int b) { cabbage[a][b] = 0; for(i..

https://www.acmicpc.net/problem/2583 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 주어진 직사각형 부분을 제외한 영역의 개수와 그영역들의 넓이를 구하는 문제입니다. 저는 이문제를 dfs를 통해서 해결 하였고 문제가 좌표가 수학에서의 평면좌표 형식으로 주어져서 배열에서는 돌려서(?) 생각을 하시면 될거 같습니다. 나머지는 크게 어려운 부분이 없습니다. main함수에서 dfs가 호출된 횟수가 영역의 개수이고 dfs안에서 마지막 지점에 도착할때까지 진행된 횟수가 그영역의 넓이입니다. 다음은 코드입니다. #include #include #include using namespace std; int arr[101][101]; int nextx[4] = {1, 0, -1, 0}; ..

https://www.acmicpc.net/problem/1525 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 퍼즐을 이동시켜 123/456/780 의 형태로 만드는 최소의 이동횟수를 구하는 문제입니다. 2차원 배열로 생각하면 검사 조건이 까다롭기 때문에 이를 문자열로 생각하고 bfs를 통하여 해결을 하였습니다. 우선 문자열을 입력받고 그 문자열을 큐에다가 넣습니다. 그리고 상하좌우 이동을 하여야 하는데 문자열의 인덱스를 기준으로 생각하면 좌우는 +1,-1이 되고 상하는 +3,-3이 되는 것을 알 수 있습니다. 따라서 이 조건에 의해 문자열 안에 두 문자를 swap시킨뒤 문자열을 set에 넣었습니다. 그리고 그 문자열이 이전에 set에 들어온적이 있는지 검사를 한뒤 들어오지 않았다면 큐..

https://www.acmicpc.net/problem/1987 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 R*C 칸에 알파벳들을 입력받고 좌측상단부터 출발해 이미 방문한 알파벳을 제외하고 가장 많이 방문 할 수 있는 칸을 구하는 문제입니다. 이동은 상하좌우로 가능하고 dfs를 이용하여 해결을 하였습니다. 알파벳은 문자이므로 visited 배열에 방문 여부를 판단할때 A의 아스키 코드값인 65를 각각 값에 빼주면서 체크를 한거 이외에는 특별한 부분은 없습니다. 다음은 코드입니다. #include using namespace std; char alpah[21][21]; int visited[26]; int nextx[4] = {1,0,-1,0}; int nexty[4] = {0,1,0..

https://www.acmicpc.net/problem/9663 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 N-Queen 문제입니다. N*N의 체스판이 주어졌을때 각행마다 하나의 퀸이 각각 다른퀸들의 영역에 침범하지 않고 놓여질 수 있는 경우의 수를 찾는 문제입니다. 전형적인 백트래킹 문제이며 저는 재귀함수를 이용한 dfs를 이용하여 풀었습니다. 먼저 N-Queen 문제 같은경우 행에 대해서는 신경을 쓸 필요가 없습니다. 그행에 퀸을 놓으면 아래 행으로 넘어가면 되므로 신경 써줘야 할 부분은 열과 우측으로 향하는 대각선 좌측으로 향하는 대각선 총 3가지입니다. 열 같은 경우 1차원 배열을 하나 지정하여 퀸이 놓여진 열은 다른 퀸이 놓일 수 없도록 지정해주면 됩니다. 좌측으로 향하는 대각선의 경..

https://www.acmicpc.net/problem/2468 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 n*n 배열에 지역의 높이 정보를 입력받고 비가 n만큼 올때 높이가 n이하인 영역이 잠기게되며 그때 생겨날 수 있는 영역의 개수중 최대 개수를 구하는 문제입니다. 이 문제는 dfs 나 bfs를 이용하여 풀면 되는데 저는 bfs를 이용하여 풀었습니다. 낮은 높이부터 시작하여 저는 잠기는 배열의 요소는 그냥 임의적으로 102라는 숫자로 채웠습니다. 그런다음 잠겨진 상태의 배열에서 bfs가 행해지는 횟수가 영역의 개수가 되므로 그 부분을 계속 비교해주며 최대 개수를 구하면 됩니다. 다음은 코드입니다. #include #include using namespace std; int are..