N

DFS/BFS에 관한 문제. DFS도 가능하지만 BFS 방식으로 풀었다. 우선 큐가 필요하다. 그리고 방문 여부를 확인하는 bool형 배열 visited, 그래프를 이어주는 bool형 배열 check를 선언하여 false로 초기화. 그리고 depth를 나타내는 int형 배열 dist도 선언하여 0으로 초기화 한다. for문으로 check 배열에 그래프를 이어준다. 사실상 상삼각행렬을 사용한다. 1부터 n까지 상삼각행렬을 그려주도록 하자. 그리고 1부터의 거리를 재야하기 때문에 큐에 1을 넣어주고, visited[1]도 true로 표시. 이제 while문으로 q가 비어잇을 때까지 반복한다. q의 앞부분을 가져오고 pop. 2 ~ n까지 for문을 돌면서 check[현재노드][i] == true && vis..

#include #include using namespace std; int solution(int m, int n, vector puddles) { int answer = 0; int check[101][101] = {0, }; int visited[101][101] = {0, }; for(int i = 0; i < puddles.size(); i++) check[puddles[i][1]][puddles[i][0]] = -1; visited[1][0] = 1; for(int i = 1; i