Limky 삽질블로그

삼성 SW 모의 테스트 #2105 - [모의 SW 역량 테스트] 디저트 카페 https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu 사용한 개념 1. BFS탐색 2. 시뮬레이션 이 문제에서 BFS탐색을 하는데 있어 이전 탐색 방향에 따라, 현재 탐색 방향을 지정해주는 것이 포인트입니다. 즉, 문제에서 주어진 4가지 대각선 방향에 있어 이전 방향이 ↘ 방향이면, 현재 탐색할 방향은 ↙ OR ↘ 입니다. 이런식으로 각각의 이전 방향에 대한 현재 탐색 방향을 지정해줘서 사각형을 그릴 수 있도록 만들어 줍니다. 아래는 전체소스 입니다. package SWE; import java.io.Buff..

프로그래머스 #DFS - 단어변환 https://programmers.co.kr/learn/courses/30/lessons/43163?language=cpp 사용한 개념 DFS 문제입니다. 탐색가능한 단어를 찾고, 다시 탐색한 단어으로 탐색가능한 단어를 찾고.. 이 과정에서 일전에 지나왔던 단어는 다시 탐색하지 않습니다! 왜냐..무한 재귀를 돌기 때문이죠..또한, 최소탐색횟수를 구하는 문제에 철학에도 맞지 않습니다. 저는 아래와 같은 프로세스로 해당 문제를 해결했습니다. 1. 탐색 가능한 단어찾기 (알파벳 1개만 다른경우만 가능 : 중복체크를 방지하기 위해 한번 찾은 알바벳을 의미 없는 문자로 대체) 2. 탐색 가능한 단어가 일전에 탐색한 단어인지 체크(새로운 단어인 경우만 탐색) 3. 타켓을 구하면,..

백준 DFS 문제 #16234- 인구이동 https://www.acmicpc.net/problem/16234 사용한 개념 DFS 문제입니다. BFS로도 할 수 있을 것 같은데, 저는 DFS 재귀 연습도 할겸 DFS 했습니다. 연합을 이룰 수 있는 국가를 구하고, 연합 국가의 총 인구수와 국가를 나누는 간단한 DFS문제입니다. 제가 생각한 프로세스는 다음과 같습니다. 1. DFS로 조건에 맞는 연합국가를 구한다. 2. DFS탐색시 조건에 맞는 국가는 Sticker를 붙여서 연합국을 구별하도록 한다. 3. 각 연합국안에서 인구이동 실시. 4. 1-3 계속 반복...더이상 인구이동이 없을 때까지... 딱히 어려운건 아니였으나...시간차를 두고 풀어봤는데, 다르게 소스를 짰네요...ㅎㅎ.. 간혹 시간초과가 뜨는..

백준 DFS 문제#2606 - 바이러스(Virus) https://www.acmicpc.net/problem/2606 사용한 개념 DFS깊이탐색을 이용했습니다.문제를 보면, 결국 무조건 1과 연결되어 있는 컴퓨터 갯수를 새는 것입니다. 컴퓨터 1과 연결되어 있으면 계속 깊이탐색을 해서 연결된 컴퓨터 갯수를 카운트하면 답은 쉽게 나옵니다. 컴퓨터 1과 연결되어있지 않는 또 다른 네트워크 영역은 신경쓸 필요도 없습니다. 따라서 소스에서 보면 알 수 있듯이 DFS(1)을 주어 무조건 시작은 1번 컴퓨터에서 시작함을 알 수 있습니다. DFS 기본 개념을 이해하면 쉽게 풀수있고 DFS를 잘 모르면, 어렵습니다.저는 기본적으로 인접리스트 방식의 DFS 깊이탐색을 했습니다.혹, DFS 기본개념을 모르시면 아래 링크에..

백준 DFS 문제 #2667 - 단지번호붙이기 https://www.acmicpc.net/problem/2667 사용한 개념 1) DFS 저는 깊이탐색을 사용했습니다. 우선, 2차원 배열에서 0이 아닌 1인 경우에 깊이탐색을 시작하여 인접해있는 1을 모두 찾게합니다. 그 다음 다시 탐색을 이어가 0이 아닌 1인경우 다시 깊이탐색을 시작합니다. 여기서 달라지는 점은, 이미 탐색을 했다라는 표시를 하기 위해 임시 변수 값이 CNT의 값을 증가시켜 해당 값으로 매핑시켜 표시합니ㅁ다. 따라서.. 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 인 경우, 2 2 0 0 0 2 0 0 0 0 0 0 0 3 3 4 4 0 3 3 0 4 0 0 3 위와 같이 매핑되는 것입니다...

안녕하세요. 림키입니다. 오랜만에 글을 쓰네요.. 요새 너무 바뻐서 ㅠㅠ... 이번 시간은 그래프를 탐색하는 방법 중 하나인 깊이탐색 DFS(Depth First Search)에 대해서 알아보도록 하겠습니다. 깊이탐색 DFS(Depth First Search)은 저장된 그래프의 모든 정점을 1번 방문하는 방법 중 하나입니다. 깊이탐색 DFS(Depth First Search)은 스택을 이용하며, 갈 수 있는 만큼 최대한 많이 가고 갈 수 없을 경우 이전 정점으로 돌아가서 다시 탐색을 하는 녀석입니다. 저는 먼저 코드를 바탕으로 설명을 하고자 합니다. 다른 블로그에는 설명 이후 코드를 하지만 반대로 해볼까 합니다. 그래프를 저장하는 방법에는 크게 3가지가 있습니다. 인접행렬, 인접리스트, 간선리스트.. 저..