https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알파벳 한글자만 변환해서 target 단어에 도달하는 bfs문제이다. 완전탐색이 아니라 bfs 카테고리에 분류된 이유는 다음과 같다. 1. hit -> hot -> lot, dot ,, 2. lot -> log -> cog 2. dot -> dog -> cog 처럼 탐색이 진행되기 때문이다. 단어를 비교하여 오직 한 알파벳만 차이나는 경우 큐에 담아주고 bfs 탐색을 진행하면 된다. 다만 hot ..
https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 Level 3 정도의 문제지만, 백준으로 치면 다른 트릭이나 복잡한 구현이 없는 기본적인 bfs/dfs 문제라서 골드 4-5정도 될 것 같다. 아무튼, 이 문제의 풀이에 대해 알아보자 문제에서 찾고자 하는 것은 '연결된 영역의 개수' 라고 할 수 있다. n은 반드시 1 이상, 즉 주어진 그래프에는 노드 1이 반드시 존재함을 알 수 있다. 1을 기점으로, 재귀 형식의 dfs를 이용해 아..
https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그래프 문제이다 딱히 추가적으로 구현해야 할 건 없고, 양방향 그래프를 잘 입력받은 뒤 bfs로 탐색을 해주면 된다 간선에 가중치가 붙으면 다익스트라를 이용해주면 된다 from collections import deque def solution(n, edge): answer = 0 graph = [[] for _ in range(n+1)] visited = [False] *(n+1) dist = ..
https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 까다로운 조건이 없는 BFS 문제이다 한가지 팁은, 아래의 cnt 변수를 어떻게 잘 조작하면 굳이 방문 배열을 사용하지 않고도 풀 수 있다는 점을 잘 생각해보시길.. from collections import deque def solution(maps): answer = -1 dq = deque() dq.append([[0,0],1]) end_x, end_y = len(maps), len(maps[..
https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr BFS/DFS 연습용 문제이다 예시가 4,1,2,1이라고 하면, 4 -> 5 or 3 에서 5 -> 6 or 4 와 3 -> 4 or 2 ,,, 와 같은 식으로 갈 수 있다. from collections import deque def solution(numbers, target): answer = 0 q = deque() q.append([numbers[0],0]) q.append([-1*num..
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제는 0-1 bfs 문제이다. 0-1 bfs란?? 그래프의 간선에서 가중치가 0과 1로만 이루어진 bfs 문제를 말한다! 이 문제가 해당 케이스이다. -1, +1, *2 위치를 체크하는 것은 bfs와 다를 바 없으나, 가중치가 0인 간선이, 가중치가 1인 간선보다 더 앞에 삽입되어야 한다! 가중치가 0이라는 것은, 아무 cost가 없다는 것을 의미하기 때..
