옌의 로그

문제[프로그래머스] 단어 변환 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 사용 알고리즘- BFS (너비우선탐색) / 그래프 탐색- 시간복잡도 O(N² × L) (N: 단어개수, L: 단어길이) 해결방법단어 배열에 타겟이 있는지 체크 후, 없다면 바로 종료(return 0)해준다각 단어를 노드로 보고, 한 글자만 다른 단어를 간선(edge)으로 연결해 그래프를 먼저 만든다begin과 한 글자 차이나는 단어들을 시작 노드로 보고 큐에 먼저 넣은 후 BFS를 돌린다BFS는 가까운 단어부터 탐색하므로, 타겟 단어에 처음 도달한 시점의 단계 수가 곧 최단 변환 횟수가 된다소스코드사용언어 : javaimport ja..

문제[프로그래머스] 네트워크사용 알고리즘- BFS (너비우선탐색)해결방법0 ~ 200 까지의 그래프를 BFS를 통해 몇 개의 네트워크가 존재하는지 찾는다bfs를 한 번 돌 때마다 연결된 노드들은 visited = true 체크가 되므로, bfs 실행 횟수가 네트워크 개수가 됨소스코드사용언어 : Javaimport java.util.*;class Solution { public int solution(int n, int[][] computers) { int answer = 0; boolean[] visited = new boolean[n]; for (int i=0; i q = new ArrayDeque(); visited[start] =..

문제[백준] 쉬운 최단거리  사용 알고리즘- BFS (너비우선탐색)해결방법목표지점을 시작점으로 생각하고, BFS 탐색을 하면서 visited 배열에 이동거리를 갱신해준다탐색종료 후, 갈 수 있는 지점이나, 도달하지 못한 케이스를 찾아 visited 배열을 -1로 바꿔준다소스코드사용언어 : c++#include #include using namespace std;int N, M;int start_x, start_y;int map[1001][1001];int visited[1001][1001];int dir[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}}; //위, 좌, 하, 우void bfs(int y, int x){ queue> q; q.push(make_pair(y, x..

문제 [프로그래머스] 게임 맵 최단거리 사용 알고리즘 - 너비우선탐색 (Breath-First Search) 해결방법 BFS사용해서 풀면 되는데, 결국 문제에서 구해야 하는 것은 최단 경로로 이동했을 때의 길이이므로, 방문을 체크하는 visited 배열에 길이를 저장해주도록 한다 그래프에서 상,하,좌,우 로 이동이 가능하므로 4방향 이동을 간단하게 표현하기 위해 dir 배열을 만들어 사용 needVisit배열이 BFS의 큐로 보면 되고, 이때 FIFO이므로 while 루프에서 꺼낼 때 shift() 메소드를 사용해 먼저 들어온 것 부터 체크 방문하지 않은 지점 (visited배열의 값이 0) 혹은, 이미 방문한 지점이지만 현재 위치에서 한 칸 이동한 것의 길이가 더 최단일 경우 큐(needVisit)에 ..