https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DFS 문제 풀이 시 Check Point 1. 2차원 배열에서 최단 거리를 구해야하므로 dist[][]배열을 선언한다. 2. vector 형 배열은 vector.size()가 행, vector[0].size()가 열이다. 3. (1,1) 좌표에서 시작하지만 사실상 (0,0)에서부터 탐색을 시작하므로 dist[n-1][m-1] 을 확인해야한다. 4. 따라서 nx와 ny도 N,M과 동일하면 탐색하지않..

기존 문제인 숨바꼭질 문제와 유사하지만, 최단 시간에 도착한 경로의 개수를 찾아야된다는 점에서 차이가 있다. https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 따라서 해당 노드와 탐색 깊이를 모두 저장할 수 있는 pair 자료형 queue를 선언해 while loop를 실행한다. 최단 시간을 찾은 이후에도 계속해서 최단시간을 만족하는 경로를 추가해야하기때문에, Queue에 들어온 도착 노드가 최단 시간을 만족..

DFS 혹은 BFS 를 사용하여 풀 수 있는 간단한 문제. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net BFS 를 사용한 풀이 #include #include #include using namespace std; const int MAX = 101; int N, M; int answer=0; vector network[MAX]; bool visited[MAX]; deque Q; int DFS(int v) { Q.push_back(v); visit..

DFS 혹은 BFS로 풀 수 있는 문제다. 비슷한 백준 문제로는 단지번호 붙이기(2667), 토마토(7576)가 있다. https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net BFS/DFS문제에서 좌표에 관련된 문제를 풀이할 때 check point 해당 매트릭스를 저장할 인접 리스트(혹은 인접 행렬)을 선언할 것. 특정 좌표를 기점으로 주변을 탐색하는 문제의 경우 dx,dy 리스트를 선언할 것. 좌표를 저장하는 큐의 경우 자..

DFS와 BFS를 기본적으로 알 수 있었던 문제. BFS의 경우 Queue, DFS의 경우 재귀함수를 사용하여 구현하였다. https://www.acmicpc.net/problem/1260 더보기 Cheak Point 1. BFS 구현 시 Queue에 vertex를 삽입할 때에도 방문 표시를 하는 것을 잊지말자! 2. 각 vertex의 인접 node에 방문할 때 해당 for loop를 해당 vertex의 리스트 사이즈까지 하는 것을 잊지말자! 3. vertex를 방문할 때 두번 방문하지 않도록 bool 타입의 visited를 선언하고, 양방향 그래프의 경우 양쪽 모두 간선을 저장하도록 하자. #include #include #include #include #include #include using nam..