나의 코드

import sys
from collections import deque
input = sys.stdin.readline
t = int(input())

def bfs():
    queue = deque()
    queue.append((home_x, home_y))

    while queue:
        x, y = queue.popleft()
        if abs(x - dest_x) + abs(y - dest_y) <= 1000:
            print("happy")
            return
        for i in range(n):
            if not visited[i]:
                a, b = graph[i]
                if abs(x - a) + abs(y - b) <= 1000:
                    visited[i] = True
                    queue.append((a, b))
    print("sad")
    return


for _ in range(t):
    n = int(input())
    home_x, home_y = map(int, input().split())

    graph = []
    for _ in range(n):
        x, y = map(int, input().split())
        graph.append((x, y))
    dest_x, dest_y = map(int, input().split())
    visited = [False for _ in range(n + 1)]
    bfs()

 

풀이 방법

처음에는 정렬 후 그리디나 구현으로 풀 수 있을거라 생각했지만

1. 좌표가 주어지는 순서대로 이동한다는 보장이 없음

2. 좌표가 음수 값을 지닐 수도 있음

해당 문제로 인해 각 지점을 그래프의 노드로 생각하여 전체탐색 후 성공.

저작자표시

'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글

[파이썬] 백준 알고리즘 No.2583 영역 구하기  (0) 2023.02.09
[파이썬] 백준 알고리즘 No.2573 빙산  (0) 2023.02.09
[파이썬] 백준 알고리즘 No.24445 알고리즘 수업 - 너비 우선 탐색 2  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24444 알고리즘 수업 - 너비 우선 탐색 1  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24480 알고리즘 수업 - 깊이 우선 탐색 2  (0) 2023.02.08

나의 코드

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
result = [0] * (n + 1)
count = 1

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

data = [r]
while data:
    cur = data.pop(0)
    visited[cur] = True
    result[cur] = count
    count += 1

    for i in sorted(graph[cur], reverse=True):
        if not visited[i]:
            visited[i] = True
            data.append(i)

for i in result[1:]:
    print(i)

 

http://noj.am/24444 

 

24444번: 알고리즘 수업 - 너비 우선 탐색 1

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방

www.acmicpc.net

 

너비우선탐색 1 문제에 reverse=True 옵션을 추가하여 내림차순으로 bfs

저작자표시

'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글

[파이썬] 백준 알고리즘 No.2573 빙산  (0) 2023.02.09
[파이썬] 백준 알고리즘 No.9205 맥주 마시면서 걸어가기  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24444 알고리즘 수업 - 너비 우선 탐색 1  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24480 알고리즘 수업 - 깊이 우선 탐색 2  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24479 알고리즘 수업 - 깊이 우선 탐색 1  (0) 2023.02.08 
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
result = [0] * (n + 1)
count = 1

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

data = [r]
while data:
    cur = data.pop(0)
    visited[cur] = True
    result[cur] = count
    count += 1

    for i in sorted(graph[cur]):
        if not visited[i]:
            visited[i] = True
            data.append(i)

for i in result[1:]:
    print(i)

나의 코드

 

bfs로, 이전 dfs와 다르게 재귀가 아닌 반복으로 풀었다.

주어진 데이터 수가 작아 리스트 자료형을 사용했으나 방대해진다면 deque를 불러와 popleft를 사용하는것이 유리

저작자표시

'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글

[파이썬] 백준 알고리즘 No.9205 맥주 마시면서 걸어가기  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24445 알고리즘 수업 - 너비 우선 탐색 2  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24480 알고리즘 수업 - 깊이 우선 탐색 2  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24479 알고리즘 수업 - 깊이 우선 탐색 1  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.1753 최단경로  (0) 2022.03.15 
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
count = 1

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)


def dfs(r):
    global count
    visited[r] = count
    graph[r].sort(reverse=True)

    for i in graph[r]:
        if visited[i] == 0:
            count += 1
            dfs(i)

dfs(r)
for i in visited[1:]:
    print(i)

 

 

 

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양

www.acmicpc.net

오름차순 -> 내림차순으로 변경된 변형문제

저작자표시

'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글

[파이썬] 백준 알고리즘 No.24445 알고리즘 수업 - 너비 우선 탐색 2  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24444 알고리즘 수업 - 너비 우선 탐색 1  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.24479 알고리즘 수업 - 깊이 우선 탐색 1  (0) 2023.02.08
[파이썬] 백준 알고리즘 No.1753 최단경로  (0) 2022.03.15
[파이썬] 백준 알고리즘 No.5525 IOIOI  (0) 2022.03.11

+ Recent posts

티스토리툴바