본문 바로가기

깊이우선탐색7

[프로그래머스] 여행경로 문제설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 해결 방법 DFS(깊이우선탐색)을 사용해 해결할 수 있는.. 2020. 3. 24.
[프로그래머스] 단어 변환 문제설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solut.. 2020. 3. 22.
[SWEA] 2819. 격자판의 숫자 이어 붙이기 문제 4×4 크기의 격자판이 있다. 격자판의 각 격자칸에는 0부터 9 사이의 숫자가 적혀 있다. 격자판의 임의의 위치에서 시작해서, 동서남북 네 방향으로 인접한 격자로 총 여섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례대로 이어 붙이면 7자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 0102001과 같은 수를 만들 수도 있다. 단, 격자판을 벗어나는 이동은 가능하지 않다고 가정한다. 격자판이 주어졌을 때, 만들 수 있는 서로 다른 일곱 자리 수들의 개수를 구하는 프로그램을 작성하시오. 풀이방법 DFS(깊이 우선 탐색)알고리즘으로 문제를 해결 방문했던 노드를 재방문할 수 있는 길이가 7인 모든 경로를 구한다. 이 때 중복되는 숫자를 처리하는 방법은 0부.. 2020. 3. 11.
[SWEA] 1865. 동철이의 일 분배 문제 동철이가 차린 전자회사에는 N명의 직원이 있다. 그런데 어느 날 해야할 일이 N개가 생겼다. 동철이는 직원들에게 공평하게 일을 하나씩 배분하려고 한다. 직원들의 번호가 1부터 N까지 매겨져 있고, 해야 할 일에도 번호가 1부터 N까지 매겨져 있을 때, i번 직원이 j번 일을 하면 성공할 확률이 Pi, j이다. 여기서 우리는 동철이가 모든 일이 잘 풀리도록 도와주어야 한다. 직원들에게 해야 할 일을 하나씩 배분하는 방법은 여러 가지다. 우리는 여러 방법 중에서 생길 수 있는 “주어진 일이 모두 성공할 확률”의 최댓값을 구하는 프로그램을 작성해야 한다. 풀이방법 DFS(깊이 우선 탐색)알고리즘과 Backtracking(되추적)으로 해결한다. 모든 직원이 일이 중복 되지 않도록 일을 선택할 수 있는 모든.. 2020. 3. 10.
[SWEA] 7699. 수지의 수지 맞는 여행 문제 평소에 여행을 즐기는 수지는 이번에 새로운 섬에 도착했다. 이 섬은 1행, 1열로 시작해서 R행, C열까지 있으며, 총 R*C 칸으로 이루어져 있다. 수지는 지금 1행 1열에 있으며 앞으로 있을 야근을 위하여 기회 있을 때 미리 여행을 떠나려고 한다. 이 섬의 각 칸에는 알파벳이 적혀있다. 이 알파벳은 섬의 명물이고, 같은 알파벳은 같은 명물이다. 이 섬에서는 명물을 볼 때마다 요금을 지급해야 하는데 각 알파벳 명물을 처음 볼 땐 무료로 볼 수 있다. 그리고, 수지는 여행을 할 때 자신이 있는 지점의 명물을 본 후 4방향(상, 하, 좌, 우) 중 한 방향으로 1칸 이동 후 다음 명물을 보는 행동을 반복한다. 올해 SGA사 1년 차인 수지는 현재 대출빚과 카드빚에 허덕이고 있다. 따라서, 명물을 최대.. 2020. 3. 10.
[SWEA] 1861. 정사각형 방 문제 N^2개의 방이 N×N형태로 늘어서 있다. 위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N2 이하의 수 Ai,j가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다. 당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다. 물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다. 처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라. 풀이방법 DFS(깊이 우선 탐색)로 모든 경로를 찾는다. A[i][j] = x일 때, 상하좌우의 원소로 방문할 수 있는 경우는, 방문하려는 원소의 값이 x + 1이면서 방문한 적이 없어야한다. 위의 조건을 만족하는 모든 경로 중 경로의.. 2020. 3. 9.
[SWEA] 1233. [S/W 문제해결 기본] 9일차 - 사칙연산 유효성 검사 문제 사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 아래는 식 “(8/2)*(6-4)”을 이진 트리로 표현한 것이다. 임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과를 사용해서 해당 연산자를 적용한다. 사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진 트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라. 여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로, 계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다. (단, 계산이 가능한지가 아닌 유효성을 검사하는 문제이므로 0으로 나누는 경우는 고려하지 않는다. ) [제약 사항].. 2020. 3. 9.

티스토리툴바