몽셀통통의 블로그

문제https://www.acmicpc.net/problem/1941 풀기이 문제는 dfs를 사용하여 풀수 있는 문제이다맨 처음 어떻게 풀어야 할지 감이 안와서 다른 분들의 코드를 참고 했는데 7개의 위치를 먼저 뽑는 것이다이렇게 하는 이유는 dfs를 사용해야 하는데 dfs는 'ㅓ','ㅗ','ㅜ','ㅏ' 과 같은 모양은 탐색을 할 수 없기 때문에모든 경우의 수를 다 돌아야 한다일단 총 25개 중에서 7개를 뽑아야 한다. 그리고 인덱스는 행은 i/25, 열은 i%25 로 잡아주면 된다그렇게 7개를 잡아주고 이 7개가 서로 연결되어 있는지 확인해준다총 dfs를 두번 사용하였는데 1. 7개 수 모두 뽑기 2. 연결 되었는지 확인하기 로 두가지로 기능이 나뉜다아이디어 생각하기가 어려워서 그렇지 코딩은 어렵지 않..

문제https://www.acmicpc.net/problem/2529 풀이이 문제는 모든 경우의 수를 완전 탐색 해야하므로 dfs를 사용!visit 함수를 사용해서 0~9까지 각 수를 한번만 포함하는 K+1개의 숫자를 만들었다min과 max를 배열로 지정한 이유는 min에서 맨앞의 자리수가 0일수도 있기 때문이다지저분하게 짰는데 나중에 다시 보아야 겠다 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include using namespace std; int K;char arr[11];int Min[11], Max[11],visit[11],temp[11]; void cop..

코드https://www.acmicpc.net/problem/2309 풀이모든 경우의 수를 판단하는 문제이므로 dfs 사용오름 차순으로 출력해야 하므로 algorithm 라이브러리에 있는 sort 함수를 사용하여 정렬해주었다그후 visit 배열로 순차적으로 확인하고 7를 방문했을때 방문한 노드들의 합이 100인지 확인하고100이면 출력하고 프로그램을 끝낸다그게 아니라면 반환하여 계속 탐색한다기본적인 dfs 문제로 1759번 암호 만들기 (https://www.acmicpc.net/problem/1759)와 유사한 문제이다 코드1234567891011121314151617181920212223242526272829303132333435#include #includeusing namespace std; in..

문제https://www.acmicpc.net/problem/1759 풀이모든 경우의 수를 체크 해야 하므로 dfs 사용arr 배열에 주어진 알파벳을 담고 visit 배열을 사용해 어떤 인덱스를 방문 했는지 체크하였다알파벳 모음은 a,e,o,i,u로 총 5개 이며 모음이 최소 1개, 자음이 최소 2개라는 조건을 맞추기 위해 둘다 카운트한다모두 C번을 방문하였다면 모음이 최소 1개, 자음이 최소 2개라는 조건을 맞추었는지 확인하고 그렇지 않다면 반환한다만약 맞다면 visit 배열 중 1인 인덱스만 arr를 차례대로 출력해 준다. 코드12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include usi..

문제https://www.acmicpc.net/problem/2589 풀이각 섬의 가장 멀리 있는 땅간의 최소 거리를 구하는 문제 이므로 bfs 사용가장 멀리 있는 땅간의 최소 거리라는 말이 어려운데 사실 두가지 조건만 지키면 된다1) 한번 지나갔던 땅은 다시 지나가지 않을 것2) 이쪽에서 저쪽으로 움직일때 최단 거리로 움직일 것위의 두가지를 만족하는 가장 멀리 있는 땅을 구하는 방법이다 처음에 문제를 풀때 dfs로 풀어서 2)번을 만족하지 못하였다그리고 모든 각각의 땅에서 bfs를 돌려야 해서 시간 초과로 걸릴 줄 알았는데배열의 범위가 크지 않아서 무사 통과한듯 싶다 코드12345678910111213141516171819202122232425262728293031323334353637383940414..

문제https://www.acmicpc.net/problem/1261 풀이최소로 벽을 뚫고 지나가는 횟수를 구하는 것이므로 bfs 사용이번에는 덱을 이용했는데 왜냐하면 visit 배열을 사용할 것인데 만약 덱을 사용하지 않으면벽을 뚫은 최소 횟수의 방향인데도 불구하고 visit이 체크되어서 방문하지 않을 수도 있기 때문이다이를 방지하려면 다익스트라로 구현을 하던가 덱을 사용하면 된다나는 덱을 사용하였는데이때 push를 할때 벽을 뚫지 않았으면 먼저 방문해야하는 곳으로 판단하여 push_front를 사용해 앞쪽에 넣어주고벽을 뚫었으면 나중에 방문해야할 곳으로 판단하여 push_back을 사용하였다 코드12345678910111213141516171819202122232425262728293031323334..

문제https://www.acmicpc.net/problem/9019 풀이최소한의 명령어를 나열하라고 하였으므로 bfs를 사용최소 시간이 아니므로 명령어를 담을 큐도 추가로 구현해 준다이미 방문했던 숫자는 이미 최소의 명령어가 있다는 의미 이므로visit 배열을 사용해서 다시 방문하지 않게 해준다 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include#include#includeusing namespace std; int A, B;int visit[10000]; int main() { int T; cin >> T; for (i..

문제https://www.acmicpc.net/problem/1520 풀이이 문제를 처음 보았을 땐 간단한 DFS 문제인줄 알았다하지만 dfs로는 시간초과가 날 수 밖에없다 따라서 dfs+dp 문제이다1. 일단 visit 체크 배열을 -1로 모두 초기화 해준다2. 함수 func에서 2-1) x좌표와 y좌표가 범위를 넘어서는지 체크해준다 2-2) 내리막길이 아니면 지나갈 수 없는 길이므로 0을 반환해 준다 2-3) 목표 지점에 도착하면 1을 반환 2-4) 만약 visit 값이 -1이 아니면 visit값 반환 (x,y 좌표에서 있는 경로의 갯수 반환을 의미) 2-5) 4방향으로 2-1,2-2,2-3,2-4를 계속 반복하면서 모든 visit값을 저장해준다 dp는 아직 개념이 잡히지 않은 나에게는 정말 어렵다 ..

문제https://www.acmicpc.net/problem/11559 풀이어릴적에 했던 게임인 뿌요뿌요 문제이다이 문제는 dfs+시뮬레이션 문제 특징이 4개 이상이 상하좌우로 붙어 있는 뿌요는 터지고 차례로 아래로 떨어져야 한다4개 이상이 붙어있는지 확인하고 아래로 떨어지게만 구현을 잘해주면 어려움 점이 없을 거 같다 나는 틀렸던 이유가 한번 터진 뿌요들을 각각 카운트 해주는 것이 아니라현 상황에서 여러개가 터졌다면 한 번으로 카운트 해야한다 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677..

문제https://www.acmicpc.net/problem/2174 풀이이 문제는 알고리즘 개념이 필요없는 문제이다.좌표 입력 값이 특이하므로 간단하게 설정해준다(주어진 좌표값을 살짝 바꾸어 원래 좌표형식을 바꾸어 주었다)처음에는 왼쪽으로 주어져있지만 오른쪽으로 바꾸어주었다 그리고 for문을 통해서 명령어를 순서대로 진행하였다여기서 사용된 알고리즘이나 트릭은 딱히 없었다. 이 문제가 알고리즘을 쓰지 않는거에 비해 생각보다 정답률이 낮았는데그 이유에는 내생각엔 인덱스 수정이 부분부분 많이 필요해서 그런것 같다 내가 처음에 틀렸던 이유는 나는 좌표의 인덱스를 바꾸어 주어서 방향 수정을 해주지 않아도 되는데방향 수정을 하는 바람에 많이 틀렸다 두번째로 틀렸던 이유는 명령어가 'F'이고 횟수가 7번일때, 같은..