BFS7 [파이썬]baekjoon 11123: 양 한마리... 양 두마리... https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 간단한 bfs문제. dfs로도 풀 수 있지만, 영역을 구하는 문제는 bfs가 편한거 같아서 bfs로 풀었다. #가 상하좌우로 밀집해 있다면, 하나의 군집으로 체크! def bfs(start): q = [] q.append(start) arr[y][x] = "." directy = [-1, 1, 0, 0] directx = [0, 0, -1, 1] while q: nowy, no.. 2022. 12. 14. programmers 단어 변환(DFS/BFS) https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 위 문제는 begin단어가 target단어까지 몇번만에 변화를 하는지 확인하는 문제이다. 나의경우 bfs를 이용하여 풀었는데 begin단어가 변할 수 있는 words를 확인하기 위해 모든 단어들을 list형태로 다시 풀어주었고, 다른알파벳이 하나인 경우에만 begin단어를 변환시켜 target단어까지 가는데 count를.. 2022. 6. 8. programmers 네트워크(DFS/BFS) https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 위문제는 컴퓨터들의 상호된 네트워크의 갯수를 구하는 문제이다. 나의 경우 DFS를 이용하여 전체 컴퓨터를 돌며 컴퓨터마다 연결된 네트워크를 체크하며 갯수를 늘려주게 하였다. def solution(n,computers): answer = 0 visit = [0] * n def dfs(now): visit[now] = 1 for i in range(n): i.. 2022. 6. 8. programmers 타겟넘버(DFS/BFS) https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 위 문제는 numbers에 있는 모든 숫자를 이용하여 target을 만드는 경우의 수를 구하는 문제인데, +와 -연산자만 이용하여 경우의 수를 구하여야 한다. 나의 경우 dfs를 사용하여 풀이를 하였는데, numbers의 모든 숫자를 순회하기 위해 dfs의 매개변수로 인덱스(나의 경우 level)을 재귀할 때 마다 키워주었고, Sum이란 .. 2022. 6. 8. baekjoon 2589: 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net bfs와 브루스포스 알고리즘으로 한칸씩 육지를 밟을때 시간을 체크해준다. 하나의 섬(?)에서 최단거리측정하는 방식으로 최대거리를 구하면 된다. #문제에 설명이 잘 되어있습니다ㅎㅎ. 그렇다면 코드는 from collections import deque n, m = list(map(int,input().split())) arr = [list(input())for _ in range(n)] lst = [[.. 2022. 4. 26. baekjoon 2468: 안전영역 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 비가올때 장마철 물에 잠기지 않는 안전한 영역의 최대 개수를 출력하는 문제이다. 2차원 배열의 숫자들은 건물의 높이를 의미하고, 건물들의 군집?의 갯수들을 확인하여 최다군집을 구하면 된다. 비가 하나도 안왔을시, 건물군집은 1이되고 비가 건물의 최대높이까지 왔을시 건물군집은 0이된다. 난 flood fill 알고리즘을 이용하여, 비가 0만큼 내렸을때부터 건물최대높이까지 내렸을때까지 result라는 빈배열.. 2022. 4. 16. 이전 1 2 다음