백준 알고리즘 9205번 맥주 마시면서 걸어가기(python)

BFS & DFS 문제이다. 인접리스트를 행렬 형식으로 구현해서 그래프를 생성하면 쉽게 풀 수 있다.

이걸 생각못해서 1시간 넘게 뻘짓을 했다.

BFS 풀이

from collections import deque

def make_graph():
    for i in range(n+2):
        for j in range(n+2):
            if i == j:
                continue
            if abs(li[i][0]-li[j][0]) + abs(li[i][1]-li[j][1]) <= 1000:
                graph[i][j] = 1
                graph[j][i] = 1

def bfs(node):
    queue = deque()
    queue.append(0)
    while queue:
        node = queue.popleft()
        for i in range(n+2):
            if graph[node][i] == 1 and check[i] == 0:
                check[i] = 1
                queue.append(i)
        
for _ in range(int(input())):
    n = int(input())
    li = [list(map(int, input().split())) for i in range(n+2)]
    graph = [[0]*(n+2) for i in range(n+2)]
    check = [0]*(n+2)
    make_graph()
    check[0] = 1
    bfs(0)
    print("happy" if check[-1] else "sad")

DFS 풀이

def make_graph():
    for i in range(n+2):
        for j in range(n+2):
            if i == j:
                continue
            if abs(li[i][0]-li[j][0]) + abs(li[i][1]-li[j][1]) <= 1000:
                graph[i][j] = 1
                graph[j][i] = 1

def dfs(node):
    check[node] = 1
    for i in range(n+2):
        if graph[node][i] == 1 and check[i] == 0:
            dfs(i)
        
for _ in range(int(input())):
    n = int(input())
    li = [list(map(int, input().split())) for i in range(n+2)]
    graph = [[0]*(n+2) for i in range(n+2)]
    check = [0]*(n+2)
    make_graph()
    dfs(0)
    print("happy" if check[-1] else "sad")