대엉코딩

https://www.acmicpc.net/problem/11724

연결 요소를 구하는 문제 입니다..

연결요소의 정확한 정의가 나와있지 않아 감은 대충 왔으나 검색을 한번 해보고 문제를 풀었습니다.

문제를 분석 하고는 dfs로 푸는 것이 편하겠다 싶어 dfs로 풀었습니다.

정점 index 순서대로 dfs를 도는데 이미 방문한 정점이면 dfs를 돌지 않습니다.

그리고 저는 처음에 아무것도 연결되지 않은 정점은 연결요소로 count를 하지 않는 다고 생각했으나

그럴 경우도 연결요소로 count를 하셔야 합니다 (즉 , 입력(6, 0) ---정점만 6개 일경우 결과값은 6입니다.)

은근 저와같은 생각을 하신분들이 있으시리라 생각합니다.....

그 외에는 쉬운 문제입니다.

<풀이>

<코드>

https://www.acmicpc.net/problem/2178

문제를 분석해 보면 최소한의 점

시작하는위치(1,1) 과 가야하는점(N,M)은 정해져 있습니다.

어떻게 하면 최단거리로 갈 수 있는지를 구하는 문제인데

DFS로 구현할경우 시간초과의 문제를 겪을 수 있습니다.(최악의경우)

BFS 냄새가 풀풀...

BFS를 돌면서 큐에다가 다음 깊이의 점들을 모두 넣는 식입니다.

그렇게 하다가 목적지가 맞을경우 BREAK 하도록!

기본적인 BFS문제가 아닐까 싶습니다.

<MAIN> 함수 입니다.

https://www.acmicpc.net/problem/1260

DFS와 BFS를 탐색을 하는 기본문제입니다.

개념을 익히는 정도 라고 하면 되겠네요!

깊이우선 탐색을 먼저 하고 너비우선 탐색을 하면 됩니다.

이차원 배열을 통해서 점과 점이 연결되었는지 여부를 확인(간선)

간선은 입력받을떄 [x][y] =1은 물론 [y][x]=1도 넣어주었습니다(양방향 간선 이므로)

일차원 배열을 통해 방문을 했는지 여부를 확인하는 용도로 사용하였습니다.

<main> 함수

https://www.acmicpc.net/problem/2667

DFS 기본 문제 느낌이였습니다.

깊이우선 탐색입니다.

한 점(집) 을 발견하면 일단 그 집과 연결된 모든 집을 탐색하고(탐색하면서 방문 했다고 체크)

다음에 FOR문을 돌때는 집이 있어도 이미 방문되었다고 표시가 되어 있으면

DFS를 돌지 않도록 하였습니다.

MAP은 그냥 정적으로 만들었고 (N)값 범위가 정해져 있으므로 N의 최대값으로 설정 하였습니다.

체크나 출력은 N값을 이용하면 되므로..