7주차_백준 #1002, #1260, #7562 #파이썬 Ps

#1002 code

1002번 문제는 두 좌표가 주어지고 각 주어진 좌표로부터의 떨어진 거리 r1, r2도 주어진다. 즉 xa,ya에서 ra만큼 떨어지고, xb,yb에서 rb만큼 떨어진 곳을 만족하는 위치의 개수를 구하는 문제이다. 

따라서 단순히 두 원이 만나는 교점의 개수라고 생각해도 무방하다. 그래서 이 문제를 풀기 위해 두 원의 중심의 거리를 distance라 두고 이 distance가 길이와 ra,rb를 비교하며 각 경우에 따라 나누어서 조건문을 작성하였다.

import sys

def dfs(c):

    ans_dfs.append(c)

    v[c] = True

    for n in adj[c]:

        if not v[n]:

            dfs(n)

def bfs(s):

    q = []          #필요한 q, v{}, 변수 생성

    q.append(s)

    ans_bfs.append(s)

    v[s] = True

    while q:

        c = q.pop(0)

        for n in adj[c]:

            if not v[n]:

                q.append(n)

                ans_bfs.append(n)

                v[n] = True

               

n, m, s = map(int,sys.stdin.readline().strip().split())

adj = [[] for _ in range(n+1)]

for _ in range(m):

    i, j = map(int, sys.stdin.readline().strip().split())

    adj[i].append(j)

    adj[j].append(i)

for i in range(1, n+1):

    adj[i].sort()

v = [False]*(n+1)

ans_dfs = []

dfs(s)

v = [False]*(n+1)

ans_bfs = []

bfs(s)

print(*ans_dfs)

print(*ans_bfs)

#1260 code (bfs, dfs)

 

#1260 bfs dfs 재귀함수 사용

#1260 문제는 bfs와 dfs를 사용하는 문제이다. 대기업 코딩테스트에 자주 나오는 알고리즘이라고 알려져 있다. dfs는 두가지 방법이 있다. 스택을 이용하여 구현하는 방법과 그냥 재귀함수를 이용해서 구현하는 방법이 있다. 그래서 두 가지 버전으로 구현을 해보았다. bfs는 큐를 이용하여 구현할 수 있다. bfs와 dfs를 구현할 때 중요한 점은 이 노드를 내가 방문했는지를 판별하는 판별 리스트를 만들어야한다는 것이고, 스택이나 큐 즉 리스트에 쌓이는 순서와 정렬을 어떻게 해야하는 가를 잘 생각하면서 구현을 해야한다. bfs와 dfs는 많은 자료들이 유튜브 강의로도 잘 되어 있으니 참고 바란다.

#7562 code(bfs)

#7562문제는 bfs를 이용하여 문제를 풀었다. dfs를 통해 문제를 풀 수도 있지만 그것 보단 bfs를 통해 문제를 푸는 것이 더 나한테는 더 쉽게 느껴져서 bfs를 선택했다. 내 머리는 그냥 bfs가 더 풀기  쉬워보였다.. 그리고 dfs로 생각하려니까 머리가 아팠다. bfs와 dfs를 이용하여 풀 수 있는 문제가 많은 것 같다.