BBLOG

문제 링크 : https://www.acmicpc.net/problem/6603

완전탐색 문제이다.

k개의 수 중 6개를 고르는 모든 경우를 출력하는 문제였다.

아직 재귀를 이용한 완전탐색이 익숙치 않아 종만북도 다시보고 더듬더듬거리며 풀었다.

1. 우선 k를 입력 받고 k크기의 배열 s를 만들어 수들을 입력받았다.

2. 재귀함수로 0부터 k-1까지 수 중에 6개를 선택하여 ArrayList에 추가해주었다.

3. 재귀호출중에 6개를 모두 선택한 경우에는 ArrayList에 있는 값을 s배열에 인덱스로 넣어주어 출력했다.

재귀함수를 통해 집합 s의 값을 바로 선택하는 것이 아닌, 0~k-1의 수 중에서 6개를 선택하여 마지막 출력을 할때 배열 s의 인덱스로 넣어 출력하도록했는데

그 이유는 재귀호출중에 골라야 할 값들 중 최소값을 구할때 편하게 구하기 위해서 였다.

만약 집합의 값을 바로 고르는 방법을 택했다면

골라야 할 값들 중 최소값을 구할때, 제일 마지막으로 고른 값을 다시 집합에서 찾고 그 다음값을 찾아줘야하는데

그에 반해 연속된 0~k-1의 수 중에서 골라야 할 값들 중 최소값을 구하기 위해서는 마지막에 고른 값에 1만 더해주면 되기 때문이다.

뭐 아무튼 아래는 소스코드이다.

문제 링크 : https://www.acmicpc.net/problem/1987

1. 보드에 적혀있는 알파벳 입력받고

2. ArrayList 생성

3. 0,0 부터 dfs로 탐색하면서 방문한 칸수 카운트 하고 그중 제일 큰 값 max_count 변수에 저장

이 과정에서 방문한 좌표의 char값을 ArrayList에 넣어주고, 다음좌표가 방문 가능한지 확인할때는 다음좌표의 char 값이 ArrayList에 있는지 확인하여 없는경우에만 방문하도록하였다.

4. max_count 출력

이렇게 풀었다. 재귀를 사용하여 가능한 경로를 모두 탐색하는 방법으로 풀었는데

아직 재귀를 이용한 완전탐색이 익숙치가 않아서 이렇게 짜는게 맞나 싶다.

좀이상하게 짜지 않았나 싶다.

불안하긴하지만 어쨌거나 '맞았습니다!!'를 받아서 블로그에 올린다.

다른사람 코드를 찾아서 비교해보고 수정하는건 내일 해야겠다.

아래는 소스코드이다.

문제 링크 : https://www.acmicpc.net/problem/11403

1. 인접행렬을 입력받고 결과를 기록할 2차원배열 result를 생성

2. 정점의 갯수반큼 반복

각 정점별로 bfs 샐행하며 한정점에서 갈수있는 정점을 result 배열에 표시.

3. result 배열 출력

이렇게 풀었다. 그래프 캄색에는 bfs를 사용하였다.

주의 할 점이 있는데 한 정점에서 자기자신은 그냥 바로 1을 체크 하는것이 아니고, 다른 정점을 거쳐서 방문이 가능한 경우에만 1로 체크해주어야 한다.

아래는 소스코드이다.

문제 링크 : https://www.acmicpc.net/problem/11724

1. 입력받은 정점의 갯수 n으로 n x n 크기의 배열을 만들어 간선연결정보를 입력받아 저장하였다.

무방향 그래프이므로 좌표의 x, y 순서를 바꿔주면 두번 표시해주었다.

2. n크기의 1차원배열 visitied를 만들어 배열을 탐색하며 방문하지않은 정점을 대상으로 dfs를 수행하고 이경우 int형 변수 count값을 증가시켜주었다

3. 반복문이 종료된 후 count 값을 출력하였다.

dfs함수는 현재정점 값을 입력받아 간선연결정보를 저장한 배열을 보며 현재 정점과 연결되어있고 방문하지않은 정점이 있는경우 그 정점값을 넘겨주며 dfs를 재귀호출하도록 하였다.

아래는 소스코드이다.

문제 링크 : https://www.acmicpc.net/problem/2583

1. 배열크기 입력받고, 사각형갯수 입력받고

2. 배열에 사각형부분 표시해준 후에

3. 그래프 탐색알고리즘을 사용하여 사각형 이외영역의 갯수와 크기를 구하여 출력하는 문제였다

그래프탐색엔 dfs를 사용하였는데 bfs를 사용하여도 결과는 같다

이문제는 원본 배열을 수정하여도 문제푸는데 지장이 없길래

visited배열을 따로 두지않고 배열 하나에 사각형도 표시하고 방문한 지점도 표시하였다.

아래는 소스코드이다.

비오는량에 따라 안전영역의 갯수가 달라지는데 그중 가장 큰 갯수를 구하면 되는 문제이다

먼저 배열을 입력받으면서 높이값중에 최대값을 max_height 변수에 저장하였다

0부터 max_height 까지 반복 {

visited 배열 값 전부다 false로 바꿔줌

2차원배열을 탐색하며 방문하지않고 안전영역이 아닌 지점이라면 {

dfs수행

count변수 증가

}

count값 중 최대값 max_count 변수에 유지

}

max_count 출력

구조는 이렇게 잡았다. 이렇게 설명할바엔 걍 소스코드만 복붙하는게 나을것같기도하지만 그래도 소스코드만 복붙은 성의 없어보일것같아서 설명하였다.

유의할점은 dfs를 호출할때 x,y 좌표값 뿐만 아니라 비가 온 양(제일 바깥반복문의 증가변수)를 넘겨주어

비의 높이보다 낮은 지점은 탐색을 하지 않도록 하여야 한다.

아래는 소스코드이다.