손코딩

백준 2668번 숫자고르기 문제 설명2개의 행으로 이루어진 숫자들이 주어집니다. 1행은 각각 노드이고 이 노드들이 가지고 있는 숫자는 2행에 적혀있습니다. 즉, 각 노드들이 연결된 형태를 이룹니다. 이 중에서 서로 Cycle을 이루는 노드들을 찾는 문제입니다. DFS를 통해 Cycle의 조건을 만족하는 노드들을 찾아나갈 수 있습니다.  백준 2668번 숫자고르기 그림 설명Cycle조건 파악(그림1)Cycle의 조건을 파악하는 것이 가장 먼저입니다. 그림처럼 출발지점으로 다시 돌아오는 경우 Cycle이라고 할 수 있습니다. 2,3,4번은 Cycle을 이루고, 5번은 스스로 Cycle을 이루고 있습니다. 방법1 Cycle에 해당하는 Path를 통으로 등록(그림2)Cycle을 코드에서 어떤식으로 등록할까 고민..

백준 2583번 영역구하기 문제 설명표가 주어지며 직사각형 형태의 좌표가 주어집니다. 해당 좌표를 제외하고 각각의 영역의 넓이를 구하는 문제입니다. 각 영역을 탐색해서 넓이를 구해야 한다는 부분에서 DFS를 떠올릴 수 있지만 가로, 세로의 영역이 좌표처럼 주어진다는 부분과 좌표에서 특정 영역을 제외해야한다는 부분을 어떻게 풀어나갈 지가 중요한 문제라고 볼 수 있습니다. 저의 경우 DFS를 돌 떄 익숙하게 돌기 위해서 표를 뒤집는 방법을 적용했습니다. 백준 2583번 영역구하기 그림 설명그림1 - for문을 더 직관적으로 돌기 위해서 상하반전을 시켜줍니다. 이렇게 하면 평소 자주 도는 for문 형태와 같아집니다.그림2 - for문을 돌 때 좌표 형태가 어떻게 그려지는 확인합니다. 문제에서 주어지는 직사각형..

백준 2667번 단지번호붙이기 문제 설명대표적인 DFS 방식 탐색으로 볼 수 있으며 표 형태에서 DFS로 탐색해나가는 방법으로 풀어나갈 수 있을 것 같습니다.  백준 2667번 단지번호붙이기 그림 설명그림1 - 작은 테스트 케이스로 위와 같다고 구성해봅니다. 행은 i, 열은 j로 돌게됩니다.그림2 - 4방향을 각각 탐색하면서 더 나아갈 곳이 있다면 그만큼 전진시켜줍니다. dx, dy와 같이 배열형태로 나아가는 방향을 표기할 수 있습니다. 기존 i, j에 대해 dx, dy를 각각 더해주면 표에서 다음위치로 전진하는 개념입니다 DFS를 끝마치면 하나의 단지를 찾은 개념이 됩니다. for문을 다 돌고나면 그림 3과 같은 형태로 총 3개의 단지를 찾게됩니다.  백준 2667번 단지번호붙이기 정답 코드(자바)im..

백준 11403번 경로 찾기 자바 문제풀이문제에서 가중치 없는 방향 그래프가 주어집니다. 가중치가 없다. 방향이 있다는 것만 캐치하면 될 것 같습니다.플로이드 와샬로 푸는 방법도 있는 것 같습니다만 아직 해당 알고리즘에 익숙치 않아서 DFS 방식으로 접근했습니다.N 범위는 100까지기 때문에 N2 탐색을 하더라도 시간 문제는 없어보였습니다.   백준 11403번 경로 찾기 그림 풀이위와 같은 형태 즉, arrayList를 선언해서 node를 만들고 각각의 방향 그래프를 탐색해나가는 형태로 풀었습니다. 문제에서 특정 노드가 다른 노드로 향하는 방향이 주어지기 때문에 그걸 참고해서 graph를 만들었고, 각 node들을 돌면서 방문이 가능한 node들을 표시해나갔습니다.진행 순서를 보면 이처럼 볼 수 있습니..