본문 바로가기

BFS10

[Python] 백준 16234번 : 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 문제 풀이 BFS를 기반으로 한 구현 문제이다. 문제에서 요구하는 답은 인구 이동이 몇 번 일어났는지가 아니라 인구 이동이 일어난 날짜이다. 따라서, 단순하게 몇번 실행되었는지 보다 날짜를 기준으로 카운트하는 게 중요하다 ✔️ 느낀 점 중요한 점을 놓쳐서 코드를 깨작깨작 계속 수정햇던 문제이다. 시간 복잡도는 생각한대로 해결되었다! 💻 코드 import sys ; input = .. 2023. 3. 6.
[Python] 백준 14502번 : 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 문제 풀이 그래프 탐색 + 브루트 포스 문제이다. 벽을 단 3개만 설치해서 얻을 수 있는 최선의 경우를 찾아야 한다. 완전 탐색을 통해서 3개를 설치했을 때 발생하는 모든 경우를 따지고, bfs를 사용해서 주어진 경우를 따져서 안전 구역의 개수를 따져주면 된다. 주의해야 할 점은 깊은 복사를 사용하지 않으면 원본이 훼손된다는 점이다! ✔️ 느낀 점 이렇게 따지는 경우를 어떻게 해야 할지 몰랐는데 단순하게 .. 2023. 2. 22.
[Python] 소프티어 : 이미지 프로세싱 https://softeer.ai/practice/info.do?idx=1&eid=627&sw_prbl_sbms_sn=156768 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 아주 가벼운 그래프 탐색 문제이다 (BFS) BFS로 풀었고 DFS도 가능하다. ✔️ 느낀 점 많이 그래프 탐색을 풀어봤다면 어렵지 않은 문제이다. 💻 코드 import sys input = sys.stdin.readline moves = [(1,0), (0,1), (-1,0), (0,-1)] h, w = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(h)] q = int(inpu.. 2023. 2. 20.
[Python] 프로그래머스 : 게임 맵 최단거리 https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 가벼운 BFS 문제이다. 최단거리를 따져야 하므로 생각할 것이 많다. 나는 이동할 수 있는 위치에 이동했을 때 최솟값을 넣어주는 방식으로 구현했다. 그리고 상대의 위치는 항상 끝에 있으므로 따로 계산안하고 넘겨주었다. ✔️ 느낀 점 오랜만에 시작한 알고리즘이라서 파이썬 문법에 익숙하지 못하다는게 느껴졌다. 문법에 대한 기억을 되살리는 것이 좋아보이고 새로운 것을 공부하기보단 공부한 것.. 2023. 1. 29.
[Python] 백준 18352번 : 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 💡 문제 풀이 그래프 탐색 문제이다. BFS와 다익스트라 알고리즘 2가지로 해결할 수 있다. 출발지점부터 큐에 넣고 가중치를 계산해주면 된다. ✔️ 느낀 점 코드를 짜다보니 어쩌다 보니 BFS로 구현했다. 💻 코드 import sys from collections import deque input = sys.stdin.rea.. 2022. 8. 16.
[Python] 백준 7576번 : 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 💡 문제 풀이 BFS 문제이다. BFS를 돌면서 가장 경우를 따져서 찾아내면 된다. 다 돌았는데 0이 있다면 -1을 출력하고 종료하면 되고 아니라면 가장 큰 값을 찾아서 출력하는데 1로 시작했으니 1을 빼줘야 한다. ✔️ 느낀 점 이번에 BFS/DFS를 구현하면서 많이 익숙해진 것 같다. 큰 틀 자체는 어렵지 않고 이제 어떤 방식으로 도출해 나갈지에 대해서만 생각을 하면될 것 같다.. 2022. 7. 17.

티스토리툴바