목록DFS (12)
라떼는말이야
문제 5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다. 숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오. 입력 다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다. 출력 첫째 줄에 만들 수 있는 수들의 개수를 출력한다. 예제 나의 풀이 이 문제는 전형적인 DFS 문제이다. 2021.05.23 - 너비 우선 탐색(BFS, Breadth First Sea..
문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. ..
프로그래머스 위클리 챌린지 3주차 문제입니다. 34등 했네요..! 처음 풀어보는 3단계 수준의 문제였는데 시간은 오래 걸렸지만 그래도 한층 성장한 기분입니다. (오랜만에 느껴보는 성취감) 문제 설명 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다. 조각은 한 번에 하나씩 채워 넣습니다. 조각을 회전시킬 수 있습니다. 조각을 뒤집을 수는 없습니다. 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다. 다음은 퍼즐 조각을 채우는 예시입니다. 위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른..
DFS의 용도 깊이 우선 탐색은 BFS와 마찬가지로 그래프를 방문하거나 탐색하는 방법 중 하나이다. 2021.05.23 - 너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현 너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현 BFS (너비 우선 탐색, Breadth First Search) 최단 거리, 최소 비용과 같이 최솟값과 관련된 문제 해결에 사용. 이때 그래프의 가중치(시간, 비용, 거리 등)가 1이어야만 한다. 모든 경로에 대한 동시 탐색 latte-is-horse.tistory.com DFS는 주로 완전 탐색이나 백트래킹과 같이 탐색의 횟수 (그래프의 최대 경로)가 정해져 있거나 예측 가능한 경우에 주로 사용한다. DFS의 과정 방문한 정점에..