Bonfire

프로그래머스 네트워크이 문제는 네트워크 개수를 구하는 문제로 주어진 연결관계를 따라 연결 여부를 확인하고, 연결된 네트워크내의 컴퓨터들을 모두 방문처리하고, 아직 방문처리 되지 않은 컴퓨터에서 다시 시작해서 연결된 네트워크들을 반복 탐색한 수만큼 세주면 된다. 나는 연결된 네트워크를 탐색하는 알고리즘으로 bfs를 활용했다.나의 코드from collections import dequedef solution(n, computers): visited=[False for _ in range(n)] answer = 0 for i in range(n): if not visited[i]: visited[i]=True answer+=1 ..

프로그래머스 단어 변환이 문제는 bfs를 활용하여 해결하였다.bfs의 특징인 가까운 거리를 먼저 찾는 특징을 활용할 수 있어 쉽게 풀었던 것 같다.논리는 queue에 시작 단어를 넣고, 다른 단어들을 비교하며, 한번도 변환되어본 적 없는 "1글자만 다른 단어"를 체크하며 다시 queue에 넣어주는 방식이다. 나의 풀이 from collections import dequedef solution(begin, target, words): visited={} for w in words: visited[w]=0 visited[target]=0 visited[begin]=1 def bfs(start): que=deque() que.append(star..

프로그래머스 아이템 줍기오늘의 문제는 DFS/BFS 문제!생각보다 어떻게 풀어야할지, 외곽을 어떻게 알아내고 교차점을 어떻게 처리하는지가 가장 포인트가 되는 문제였던것 같다.풀때까지 아직 해답을 잘 모르겠지만, 우선 72점정도 획득한 코드를 공유해 본다.나의 코드from collections import dequedef solution(rectangle, characterX, characterY, itemX, itemY): max_x=0 max_y=0 for x1,y1,x2,y2 in rectangle: max_x=max(max_x,x1,x2) max_y=max(max_y,y1,y2) graph=[[0 for _ in range(max_x+2)] for _ ..

프로그래머스 퍼즐조각 나의 풀이 (81% 상태) 1. bfs를 통해 빈칸 집합을 A에 그리고 조각들의 좌표 B에 모아본다.2. 빈칸집합이나 조각들을 좌상단으로 정렬시켜준다.3. 빈칸과 조각들을 매칭시켜보면서 확인한다.4. 매칭시 조각구성 수를 세서 answer에 모두 더해준다. from collections import dequedef solution(game_board, table): # 모양 좌표 찾기 def bfs(board,row,col,val): if visited[val][row][col]: return visited[val][row][col]=True if board[row][col]!=val: retur..

오늘 주어진 문제는 전력망을 둘로 나누기 문제였다.풀이이번 문제도 1일차와 동일하게 완전탐색 알고리즘으로 풀 수 있는 문제였다.주어진 wires의 간선을 하나씩 제외해보며, 체크해보고, 가장 차이가 작은 수를 출력하면 된다.나는 BFS 알고리즘을 활용하여 1번 송전탑에 연결된 송전탑들을 센 후, 전체에서 빼서 비교한 다른 송전탑 집합과의 차이를 계속 비교하는 방법으로 쉽게 풀었다. from collections import dequedef solution(n, wires): def bfs_and_difference(k): graph=[[] for _ in range(n)] visited=[False for _ in range(n)] for i in ran..