[2022 하계 모각코] 팀 "한 명 어디갔노" 4회차 - 계획 및 결과

목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.

사용 언어
Python

일정
4회차: 7/27 14:00 ~ 17:00
목표 : 백준 DFS 알고리즘 관련 3 - 4 문제 풀기

1. 백준 1967번
   

Code

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n = int(input())
graph = [[] for _ in range(n + 1)]


def dfs(x, weight):
    for i in graph[x]:
        a, b = i
        if distance[a] == -1:
            distance[a] = weight + b
            dfs(a, weight + b)


# 트리 구현
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
    graph[b].append([a, c])

# 1번 노드에서 가장 먼 곳을 찾는다.
distance = [-1] * (n + 1)
distance[1] = 0
dfs(1, 0)

# 위에서 찾은 노드에 대한 가장 먼 노드를 찾는다.
start = distance.index(max(distance))
distance = [-1] * (n + 1)
distance[start] = 0
dfs(start, 0)

print(max(distance))

결과

2. 백준 2668번
   

Code

N = int(input())			# 입력
arr = [0]				# 두번째 줄 숫자 담을 리스트.
for _ in range(N):
    arr.append(int(input()))
answer = set()				# 결과 담을 set

# dfs 정의
def dfs(first, second, num):
    first.add(num)			# 첫번째 줄 집합에 num 추가
    second.add(arr[num])		# 두번째 줄 집합에 arr[num] 추가
    if arr[num] in first:		# arr[num]이 첫번째 줄 집합에 있을 때
        if first == second:		# 첫번째 줄 집합과 두번째 줄 집합이 같다면
            answer.update(first)	# 결과 업데이트
            return True
        return False
    return dfs(first, second, arr[num])	# 아니라면 다음 dfs 실행

# dfs 실행
for i in range(1, N+1):
    if i not in answer:			# i가 결과 집합 안에 없는 경우만 실행
        dfs(set(), set(), i)

print(len(answer))
for s in sorted(answer):
    print(s)

결과

3. 백준 3109번
   

from sys import stdin

r, c = map(int, stdin.readline().split())
area = [list(map(str, stdin.readline().strip())) for _ in range(r)]
visit = [[False] * c for _ in range(r)]
dx = [-1, 0, 1]  # 우상 우 우하
dy = [1, 1, 1]
result = 0


def go(a, b):
    if b == c - 1:
        return True
    for j in range(3):
        nx = a + dx[j]
        ny = b + dy[j]
        if (0 <= nx < r) and (0 <= ny < c) and not visit[nx][ny] and area[nx][ny] == '.':
            visit[nx][ny] = True
            if go(nx, ny):
                return True
    return False


for i in range(r):
    if area[i][0] == '.':
        if go(i, 0):
            result += 1
print(result)

결과