dfs

17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net 풀이 과정 해당 문제는 DFS로 접근하였습니다. 똑같은 경로로 방문할 경우가 있을 때는 DFS로 접근하는 편이라,,😊 1. n, m 그리고 미로 그래프를 입력받는다. 2. 방문 표시를 하기 위해 "visited" 이름으로 n x m 크기의 배열을 생성한다. 3. n x m 만큼 반복문을 돌려준다. 해당 (i, j) 좌표로 시작하는 경로로 탐색한 경우가 없을 경우 dfs 탐색 시작. 4. DFS 탐색 4-1) 현재 좌표 값(x, y)이 미로를 탈출할..

17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 해당 문제는 정말 주어진대로 문제를 풀었습니다. 똑같은 곧을 방문한 적이 있으면 출력 값을 1 더해주고 반환해주고, 개미 놈이 이동할 수 있는 경우를 다 설정하여 해당 방향에서 양 갈래 길로 가는 경우로 dfs 탐색을 해주었습니다.. 하지만 python으로는 이렇게 주어진 대로 문제를 해결하면 시간 초과가 발생하네요.. 경우의 수가 1부터 22까지이기 때문에 미해결 코드로 1부터 22까지 출력해서 밑에 코드로 제출했더니 통과가 되었네요.. print(..

19641번: 중첩 집합 모델 S번 노드가 루트 노드일 때, 번호가 가장 낮은 노드부터 오름차순으로 방문해서 중첩 집합을 구성했을 때, 각 노드의 번호 left 필드와 right 필드를 출력한다. 총 N개의 줄에 걸쳐 i번째 줄에 i번 www.acmicpc.net 풀이 과정 만약 문제가 잘 이해 안 된다면 표를 잘 보시면 됩니다. 😊 표의 예시에서 "HI-ARC"가 root 노드로 시작됩니다. 그러기 때문에 root 노드 "HI-ARC"의 왼쪽 노드는 order을 1로 가집니다. 그 이후에 "HI-ARC"와 연결된 노드를 찾습니다. 표에서는 "경영 지원실"이 제일 빠른 노드입니다. 해당 "경영 지원실"의 왼쪽 노드는 다음 order인 2를 가집니다. "경영 지원실"과 연결된 노드... 노드... 연결된 ..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 과정 - 모든 노드들은 ABCDE 친구 관계가 성립하는지 그래프 탐색을 한다. - 방문한적이 없는 노드는 해당 DFS로 탐색하고 깊이를 1 증가 시킨다. 깊이가 총 5번이면 관계가 성립 되었기에 ans 값을 true로 설정하고 return 해준다. - dfs로 탐색이 끝났는데 ans 값이 false 면 해당 탐색했던 노드는 다시 방문 표시를 false로 설정한다. #include #include #include using namespace std; int n,m; map friends; vector visited; bool ans = false; void dfs(..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 과정 - 퀸은 가로, 세로, 대각선으로 나아갈 수 있는 말이다. 즉, 퀸 하나를 놓으면, 그 퀸과 같은 가로, 세로, 대각선에는 또 다른 퀸을 놓을 수 없다. - 해당 문제는 dfs의 재귀 호출로 해결하였으며, 2차원 배열과 1차원 배열 두 가지로 해결을 하였다. 1차원 배열을 사용하는 게 미숙하여 다른 블로거님들의 풀이를 보면서 이해하면 문제를 풀었고 혼자 풀 때는 1차원 배열을 풀어야겠다는 생각을 못하여 2차원 배열로 해결하였다. - 0번째 행부터 각 행에 대해 각각 ..

코딩테스트 연습 - 5주차_모음사전 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 나올 수 있는 경우의 수가 10000 이하이기 때문에 DFS로 충분히 시간복잡도 생각하지 않고 풀 수 있다. alpha 라는 모음 값이 저장되어 있는 배열을 만들어서 나올 수 있는 모든 경우의 수를 map 함수를 이용해서 저장한다. 단순 구현 문제. #include #include #include using namespace std; int count =1; vector alpha = {"A","E","I",..

코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 문제를 보자마자 DFS와 BFS를 떠올렸고, DFS가 더 자신있기에 DFS로 문제를 풀기로 결심했다. 처음 가볍게 코드를 짰고 주어진 테스트케이스가 운좋게 통과되었지만 제출하는 동시에 50..

코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 장소안에서 'P'가 나올 시 해당 i와 j 값에 대해서 방문 표시를 하고 DFS 탐색을 한다. DFS에서는 해당 문자열 벡터와 방문 bool 함수와 'P'의 좌표 마지막으로 deep이라는 매개..