0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 조건과 같은 친구 관계가 있는지 구하는 문제이다. DFS로 친구를 찾아가고 중간에 기존에 있었던 친구가 나오면 탐색을 중단하는 백트래킹을 사용하면 된다. 친구 추가 a,b가 입력됐을때 a와 b는 서로 친구이므로 a, b 모두 친구 리스트에 push 해준다. vector v[2001]; vector check(2001, false); for(int i = 0; i > a >> b; v[a].push_back(b); v[b].push_bac..

문제 출처 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 백트래킹을 사용하여 쉽게 해결할 수 있다. dfs로 가장 간단하게 탐색을 진행할 수 있다. 그러나 dfs로 4칸을 모두 찾는 단순한 문제인줄 알았는데, ㅓ ㅜ ㅓ ㅗ와 같은 케이스가 있다. 이 경우는 따로 처리하여 해결하였다. 코드 #include #include using namespace std; int N, M; int dx[4] = {1, -1, 0 , 0}; int d..

문제 출처 : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 dfs를 사용하여 해결한 문제이다. 그래프 문제에서 자주 쓰는 dx, dy 배열을 선언해 4방향 탐색을 돌려주면 된다. 여기서 주의할 점이 다음 dfs를 호출할때 cnt + 1, cnt++, ++cnt 에 따라 결과값이 달라진다는 것에 유의하자. dfs(row + dy[i], col + dx[i], cnt + 1); 코드 #include #include using nam..