[python] 백준 1697 : 숨바꼭질

[python] 백준 1697 : 숨바꼭질 1697번: 숨바꼭질 (acmicpc.net) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 실버 1 그래프, BFS 접근 일차원으로 이동할 수 있는 bfs문제이다. 5를 노드라고 생각했을 때, 5가 탐색할 수 있는 노드는 4, 6, 10이된다. 각각의 노드는 [3, 5, 8], [5, 7, 12], [9, 11, 20]을 탐색할 수 있을 것이다. 여기서 미리 방문했던 노드는 방문하지 않도록 해야하며 노드가 일차원 이동을 하기 때문에 문제..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 3.
• textsms

[python] 백준 1325 : 효율적인 해킹(BFS)

[python] 백준 1325 : 효율적인 해킹(BFS) 1325번: 효율적인 해킹 (acmicpc.net) max_hack: max_hack = h hack.append([i, h]) for i, cnt in hack: if cnt == max_hack: print(i, end = ' ') 어차피 1번부터 n번까지의 노드를 돌아가면서 bfs를 돌리기 때문에 나오는 순서대로 최댓값에 해당하는 노드를 출력하면 된다.

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 5. 2.
• textsms

[python] 백준 1743 : 음식물 피하기(BFS)

[python] 백준 1743 : 음식물 피하기(BFS) 1743번: 음식물 피하기 (acmicpc.net) 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 실버 1 그래프, BFS 접근 이차원 배열을 사용하여 그래프를 구성하고 좌표를 한칸씩 이동하면서 음식물의 크기를 계산한다. bfs탐색이 끝나면 해당 음식물의 크기에 대한 계산이 끝난 것과 같으므로 각 bfs탐색의 반환값중 가장 큰 값을 출력하도록 한다. 코드 import sys; input = sys.stdin.r..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 28.
• textsms

[python] 백준 18352 : 특정 거리의 도시 찾기(BFS)

[python] 백준 18352 : 특정 거리의 도시 찾기 18352번: 특정 거리의 도시 찾기 (acmicpc.net) 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 실버 2 그래프, BFS 접근 단방향 그래프 구현과 특정 정점으로부터의 거리를 구현할 수 있으면 쉽게 풀 수 있는 문제이다. 코드 import sys; input = sys.stdin.readline from collections import deque def bfs(no..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 27.
• textsms

[파이썬] 백준 2667 : 단지 번호 붙이기(BFS)

[파이썬] 백준 2667 : 단지 번호 붙이기(BFS) 2667번: 단지번호붙이기 (acmicpc.net) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 실버 1 그래프, BFS 접근 그래프 이론 문제중에 양이라는 문제와 비슷한 유형이다. 지정된 범위안에서 좌표에 따라 bfs 탐색을 시키면서 1이 있을때마다 그 개수를 카운팅한 후 반환하면 집의 개수를 출력하도록 할 수 있다. bfs 탐색이 종료될 때마다 집의 개수를 반환하므로, 이는 곧 단지 하나에 대한 탐색을 끝마쳤다는 뜻과 같기 때문에 집의 개수를 담을 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 16.
• textsms

[파이썬] 백준 11725 : 트리의 부모 찾기

[파이썬] 백준 11725 : 트리의 부모 찾기 11725번: 트리의 부모 찾기 (acmicpc.net) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 실버 2 그래프, BFS 접근 이 문제는 그래프 이론을 이해한 사람이면 누구나 바로 풀어낼 수 있는 문제라고 생각한다. 실버 3으로 강등해도 괜찮은 것 같다. 방문 처리를 할때 부모의 노드 번호를 새겨주고 2~N까지의 방문 처리 값을 출력하면 끝이다. 코드(BFS) import sys; input= sys.stdin.readline from collections import deque def bfs(node): queue ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 12.
• textsms