BFS7 2606.바이러스 python https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net bfs 를 사용한 간단하다 딕셔너리로 어디에서 어디가 이어지는지 만들고 재귀함수로 방문 가능한곳을 모두 집합에 넣어서 그 집합의 크기가 바이러스 퍼지는 크기다 d={} input() n=int(input()) for i in range(n): i=list(map(int,input().split())) d.setdefault(i[0],set()) d.setdefault(i[1],set()) d[i[0]].. 2023. 5. 6. 2146.다리 만들기 - python https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net dfs/bfs를 응용하는 문제 기본적으로 섬의 개수나 크기는 한 번에 간단하게 끝나지만 이건 그 두 가지를 조합해서 풀어야 한다 섬의 거리를 구하는 방법은 각각 섬의 가장자리에서 시작해 가장 가까운 섬까지의 거리를 측정해야 한다. 섬의 가장자리를 구하는 방법은 일반적인 섬의 크기 구하는 방식처럼 한 칸씩 움직이다가 바다가 나오면 멈춤 그곳이 가장자리다. 그리고 다음 섬까지의 거리는 가장자리에서 시작해서.. 2023. 4. 20. 리코쳇 로봇 https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각보다 어렵다 일단 이것도 2차원 형태로 길을 찾는 문제다 그러면 bfs 사용 아마도 dfs 보다 bfs 가 빠를 듯 n 번째에 출구를 찾으면 바로 끝나기 때문에? 어쨌든 bfs를 사용하는데 약간 방식이 애매하다 한 칸이 아니라 끝까지 미끄러지기 때문에 처음 시작점에서 시작해서 사방으로 가는데 1칸이 아니라 벽을 만나거나 모서리까지 갈 때까지 while 문으로 반복한다 만약 while 문을 탈.. 2023. 4. 12. 1020. Number of Enclaves - python https://leetcode.com/problems/number-of-enclaves/ Number of Enclaves - LeetCode Can you solve this real interview question? Number of Enclaves - You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell. A move consists of walking from one land cell to another adjacent (4-directionally) land leetcode.com leetcode는 데일리 문제가 약간 비슷한 유형에서 나오니까 어제와 같은 bfs 문제.. 2023. 4. 7. 1254. Number of Closed Islands - python https://leetcode.com/problems/number-of-closed-islands/description/ Number of Closed Islands - LeetCode Can you solve this real interview question? Number of Closed Islands - Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, leetcode.com 아마 제일 많은 거 같은 문제 유형 bfs/dfs 일단 .. 2023. 4. 6. 7569.토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이제 전설의 토마토의 정체가 밝혀진다 내가 처음 풀었던 bfs/dfs 문제다 처음에는 뭔지 모르고 풀었지만 알고 보니 bfs였다 이때 만든 코드가 기본이 되어서 점차 발전하고 지금은 이 토마토와 문제는 쉽게 풀 수 있다 고맙다 토마토 하지만 먹지는 않는다 2023. 3. 25. 10026.적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 일반적인 bfs 문제 2차원 이상 행렬이 주어지고 어디 길을 찾던지 섬의 개수 그런 거 이런 모든 형태에 적용하는 하다 이게 알고리즘의 힘인가 어쨌든 토마토에게 고마워하자 다른 건 다 같은데 2가지 경우라 리스트도 2개 만들었다 지나가면서 길에 x 표시를 하는 거라 2번 돌리면 맵이 망가져있어서 2개로 해줘야 함 그리고 색칠한 부분의 개수니까 그냥 한 번이라도 함수가 실행되면 한 개의 구역.. 2023. 3. 23. 이전 1 다음