# BFS
백준 2146 다리만들기
문제링크 https://www.acmicpc.net/problem/2146 문제 풀이 섬과 섬의 구분을 위해 각 섬에서 bfs를 이용해 넘버링을 해주었습니다. 모든 섬에 대해 다시 bfs를 실행해 다른 섬에 도착하는 최단 거리를 측정 하였습니다. 시행착오 없었습니다. 코드 후기
[프로그래머스] LV.3 단어변환 (JS)
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.예를 들어 begin이 "hit", target가 "cog", words가 "hot"
[BOJ]16959. 체스판여행
BOJ 16959 문제 바로가기문제의 저작권은 백준 온라인저지에 있습니다.처음 시작하는 좌표가 0,0이라는 보장이없다는것을 모르고 틀렸었다,,, 이점 잘 확인하자
BOJ 19238 : 스타트 택시 - C++
주의board\[]\[]와 cost\[]\[]를 인덱스 1~N까지 사용하는데 초기화를 0부터 함\--> 아래처럼 해야 1부터 N까지 초기화가 된다for(int i=1;i<=N;i++) fill(cost\[i]+1, cost\[i]+N+1, -1);예외처리고객을 태
리스트와 매트릭스를 이용한 BFS 접근방식
방향이 있는(양방향) 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.각 정점(vertex)의 종류와 개수를 확인한다.연결관계를 리스트나 매트릭스 방식으로 지정해준다.리스트: {0:\[1], 1:\[0], 2:\[3]
백준 1463번 ) 1로 만들기
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의
백준 2638 치즈
문제링크 https://www.acmicpc.net/problem/2638 문제 키포인트 가장자리는 치즈가 놓이지 않으므로 가장자리에서 부터 BFS나 DFS를 실행해줍니다. (아래 코드는 bfs 이용) 0인 부분(치즈가 없는 영역)은 방문하지 않았다면 큐에 넣어주고 1인 부분(치즈가 있는 영역) 은 큐에 넣지 않고 해당 좌표의 값을 1증가 시켜줍니다. 큐...
[JS] Q15 특정 거리의 도시 찾기
어떤 나라에는 1~N번까지의 도시와 M개의 단방향 도로가 존재합니다. 모든 도로의 거리는 1입니다. 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하세요. 또한 출발 도시 X에서
[JS] 미로 탈출
동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하여 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로,
DFS와 BFS
DFS란?BFS란?그래프에서 적용된 모습차이점 비교DFS는 Depth-First Search의 약자로 깊이 우선 탐색이란 뜻입니다.트리에서 사용한다면 다음과 같은 순서를 가집니다.선택 가능한 자식 노드가 없을 때까지 자식 노드를 우선적으로 선택합니다.모든 노드를 탐색해
"순위" 문제 풀이
요즘 Jest와 다른 공부들을 하다보니까 시간이 모자라 하루에 한 문제씩 풀지 못하고 놓치는 경우가 생기고 있다... ㅠ ㅠ시간관리를 잘 하지 못한 내 핑계지만 놓친만큼 주말에 최대한 맞춰야겠다.이번 문제는 처음에는 어떻게 이거를 그래프로 풀지 싶었는데 고민하다보니까
BOJ 17142 : 연구소 3 - C++
핵심: next_permutation을 이용해서 전체 virus개수 중 M개를 선택하는 조합을 모두에 대해 전부 바이러스를 퍼뜨리는 경우 중 최소값을 기록시간복잡도 최대 10개의 바이러스 중 5개를 선택하는 수이기 때문에 252가지 경우를 가진다252가지 경우에 대해
BOJ 16236 : 아기상어 - C++
로직shark의 좌표를 시작으로 BFS를 수행해서 가장 가까운 좌표를 찾는다ans를 증가시키고 shark를 update!느낀 것 : 문제의 조건을 정확하게 파악하지 못해서 시간이 오래걸렸기 때문에 정신을 차려야 한다
2206 벽부수고이동하기
문제링크현재상태를 계속해서 큐에 집어넣어주고 벽을 부쉈는지에대한 visit배열을 한차원 늘려서 확인해준다.이외의 중요팁들은 백준 게시판에서 글을 가져와보았다.
