너구리의 코딩 블로그

풀이 쉽게 생각했지만 생각보다 시간을 많이 들인 문제입니다. 저는 이 문제를 풀이할 때 DFS를 이용하여 풀이하였습니다. 6개의 매개변수 (i, j(현재위치), si와 sj(시작점), 0(방향 0), 1(길이 1))를 이용하였습니다. 항상 직사각형 모양으로 디저트 카페 투어가 이루어지므로 저는 가장 위쪽 모서리를 중심으로 잡고 오른쪽 아래↘ (dir==0), 왼쪽 아래↙ (dir==1), 왼쪽 위↖(dir==2), 오른쪽 위↗(dir==3) 이렇게 기준점에서 시작하여 ↘ ↙ ↖ ↗순서대로 순회한다면 원위치로 돌아올 수 있기 때문입니다. 이를 이용하여 DFS를 순회하게 되는데, 해당 위치의 디저트 번호를 방문했는지 확인하는 disert()배열과 함께 이동하였습니다. 먼저 방향이 0일때, 오른쪽 아래(↘)로..

문제 풀이 빙산이 두 덩어리 이상으로 나뉘는 데에 걸리는 시간을 구하는 문제입니다. 이 문제를 풀이할 때 사용한 주요 로직은 위와 같습니다. while문을 이용해 빙산의 조각이 두 덩어리 이상으로 나뉘거나, 모두 녹아 사라질 때까지 반복합니다. 1. melting() : 빙산이 사라질 만큼을 계산해주어야 합니다. 계산을 위해 사용할 배열 copy를 만들어 준 뒤, 상, 하, 좌, 우에 위치한 0을 카운트하여 copy 배열에 저장해주었습니다. 2. calc() : 사라질 빙산이 계산되었다면, copy 배열의 정보를 이용해 빙산을 없애주었습니다. 빙산의 양보다 사라질 양이 많다면 0으로 저장하도록 해주었습니다. 3. checkLand() : 빙산의 덩어리 수를 계산하는 함수입니다. BFS를 이용하여 현재 맵..

출처 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 이 문제는 DFS를 이용하여 풀이하였습니다. 항상 0에서 출발하여 99로 도착하므로 저는 99를 출발점으로 설정해준 뒤 DFS 탐색을 통해 0을 찾는다면 1을 출력해주고, 아닌 경우에는 0을 출력하도록 하였습니다. 2차원 배열을 boolean 타입으로 만들어주었고 방문한 지점에 대해서는 ( visited = false ) 다시 방문하지 않도록 하여 답을 찾을 수 있었습니다. BFS나 DF..

문제 그림과 같은 그래프에 대하여 정점의 개수 N, 연결선의 개수 M이 주어지고 그래프에 대한 연결 정보가 주어질 때, 시작 정점 1에서 DFS 방문 경로를 출력하시오. 풀이 DFS를 연습하는 가장 기본적인 문제입니다. 시작 정점 1을 dfs() 함수 실행할 때 입력해준 뒤, Stack을 이용하여 다음 정점과 연결되어 있고 ( map[x][i] == 1 ), 아직 방문하지 않은 정점이 있다면 ( visited[i] == false ) 스택에 해당 정점을 넣어주고, 더 이상 방문할 정점이 존재하지 않는다면 pop()을 해주면서 연결되어 있는 모든 정점을 깊이 우선 탐색(Depth First Search)으로 방문하는 문제입니다. 방문한 정점에 대하여 중복 방문하는 경우를 방지하기 위해 visited 배열을..

문제 풀이 먼저 dfs에서 이동 가능한 경로는 ↗ → ↘ 이므로 di 배열은 { -1 0 1 } 로 선언해주었습니다. 그 다음 항상 가장 왼쪽 열에서 출발하므로 for문을 통해 dfs( i , 0 ) 으로 동작시켜주었습니다. 문제 풀이에서 가장 중요한 부분은 문제에 있는 힌트 그림인 것 같습니다. 파이프가 중복이 불가능하기 때문에 dfs로 이동을 하다가 만약 더이상 진행이 불가능하다면 ( dfs 함수 속 for 문이 모두 종료된다면 ) 해당 경로를 모두 false로 반환해주어야 합니다. 문제 풀이 시에 이 부분 때문에 한참 헤맸습니다. 앞으로 계속 진행이 가능한 경우 dfs( next_i, next_j ) 를 통해 next_j 가 M - 1에 도달할 때까지 진행 시켜주고 오른쪽 끝 열에 도착할 경우 cn..