[알고리즘 기초 2/2] 그래프

13023번: ABCDE

시간초과로 3번 연속 틀렸다.
아래의 틀린 코드다.

import sys
input = sys.stdin.readline

n, m = list(map(int, input().split(" ")))
arr = [[0] * n for _ in range(n)]

for _ in range(m) :
    row, col = list(map(int, input().split(" ")))
    arr[row][col] = 1
    arr[col][row] = 1

visited = [0] * n
maxValue = 0

def dfs(row, length) :
    global maxValue
    maxValue = max(maxValue, length)
    if maxValue >= 5 :
        print(1)
        sys.exit()
    else :
        for i in range(n) :
            if visited[i] == 0 and arr[row][i] == 1:
                visited[i] = 1
                dfs(i, length + 1)
                visited[i] = 0

for start in range(n) :
    visited[start] = 1
    dfs(start, 1)
    visited[start] = 0

print(0)

arr에 0과 1을 통해서 해당 친구와의 연결을 표현해주었고, 그를 체크하면서 dfs를 호출했었다. 그러나 이런 방식을 사용하게 되면 for문에서 친구가 아닌 관계까지 검사를 진행해야 한다.

때문에 친구 관계만 list에 넣어놓고 for문으로 돌리면 되는 것이다.

import sys

input = sys.stdin.readline

n, m = list(map(int, input().split(" ")))
adj_list = [[] for _ in range(n)]

for _ in range(m):
    row, col = list(map(int, input().split(" ")))
    adj_list[row].append(col)
    adj_list[col].append(row)

visited = [0] * n
maxValue = 0

def dfs(node, length):
    global maxValue
    maxValue = max(maxValue, length)
    if maxValue >= 5:
        print(1)
        sys.exit()
    visited[node] = 1
    for neighbor in adj_list[node]:
        if visited[neighbor] == 0:
            dfs(neighbor, length + 1)
    visited[node] = 0

for start in range(n):
    visited[start] = 1
    dfs(start, 1)
    visited[start] = 0

print(0)

7569번: 토마토

아이디어 떠올리기는 수월했는데, 오랜만에 BFS 구현하려니까 시간이 좀 걸렸다.

import sys
input = sys.stdin.readline

n, m, h = list(map(int, input().split()))
arr = []

from collections import deque
dq = deque()

for _ in range(h) :
    tmp = []
    for __ in range(m) :
        tmp.append(list(map(int, input().split())))
        for i in range(len(tmp[-1])) :
            if tmp[-1][i] == 1 :
                dq.append([_, __, i])
    arr.append(tmp)

rl = [0, 0, 1, -1]
ud = [1, -1, 0, 0]

while dq :
    fir = dq.popleft()

    if fir[0] - 1 >= 0 : # up
        if arr[fir[0] - 1][fir[1]][fir[2]] == 0 :
            arr[fir[0] - 1][fir[1]][fir[2]] = arr[fir[0]][fir[1]][fir[2]] + 1
            dq.append([fir[0] - 1, fir[1], fir[2]])
    if fir[0] + 1 < h : # down
        if arr[fir[0] + 1][fir[1]][fir[2]] == 0 :
            arr[fir[0] + 1][fir[1]][fir[2]] = arr[fir[0]][fir[1]][fir[2]] + 1
            dq.append([fir[0] + 1, fir[1], fir[2]])
    
    for direction in range(4) :
        current_row = fir[1] + rl[direction]
        current_col = fir[2] + ud[direction]
        if 0 <= current_row < m and 0 <= current_col < n : 
            if arr[fir[0]][current_row][current_col] == 0 :
                arr[fir[0]][current_row][current_col] = arr[fir[0]][fir[1]][fir[2]] + 1
                dq.append([fir[0], current_row, current_col])
maxValue = -123

for height in arr :
    for row in height :
        if 0 in row :
            print(-1)
            exit()
        else :
            maxValue = max(max(row), maxValue)
print(maxValue - 1)

7562번: 나이트의 이동

BFS 문제임을 알 수 있다. 목표 지점과 출발 지점이 같은 경우는 연산없이 바로 result에 답인 0을 넣어주도록 처리했다.

from collections import deque
import sys
input = sys.stdin.readline

t = int(input())

r_list = [2, 2, -2, -2, 1, 1, -1, -1]
c_list = [1, -1, 1, -1, 2, -2, 2, -2]

result = []

for ____ in range(t) :
    L = int(input())
    cr, cc = list(map(int, input().split()))
    dr, dc = list(map(int, input().split()))

    if cr == dr and cc == dc :
        result.append(0)
        continue
    arr = [[0] * L for _ in range(L)]
    arr[cr][cc] = 1

    dq = deque()
    dq.append([cr, cc])
    
    while dq :
        fir = dq.popleft()

        for i in range(8) :
            rr = fir[0] + r_list[i]
            cc = fir[1] + c_list[i]
            if 0 <= rr < L and 0 <= cc < L :
                if arr[rr][cc] == 0 :
                    if rr == dr and cc == dc :
                        result.append(arr[fir[0]][fir[1]])
                        dq.clear()
                        break
                    else :
                        arr[rr][cc] = arr[fir[0]][fir[1]] + 1
                        dq.append([rr, cc])

print(*result, sep='\n')

16929번: two dots

참고 여부: O

import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
arr = []
for _ in range(n) :
    arr.append(list(input())[:m:])

# from collections import deque

visited = [[0] * m for _ in range(n)]

r = [-1, 1, 0, 0]
c = [0, 0, 1, -1]
answer = False

def dfs(row, col, cnt, start_row, start_col) :
    global answer
    if answer :
        return
    
    for i in range(4) :
        rr = row + r[i]
        cc = col + c[i]
        if 0 <= rr < n and 0 <= cc < m :
            if arr[rr][cc] == arr[row][col] :
                if rr == start_row and cc == start_col and cnt >= 4 :
                    answer = True
                    return
                elif visited[rr][cc] == 0 :
                    visited[row][col] = 1
                    dfs(rr, cc, cnt + 1, start_row, start_col)
                    visited[rr][cc] = 0

for i in range(n) :
    for j in range(m) :
        visited[i][j] = 1
        dfs(i, j, 1, i, j)
        if answer :
            print('Yes')
            exit()
if not answer :
    print('No')

14226번: 이모티콘

참고 여부: O

진짜 한참을 헤맨 문제..
visited로 이미 만족했던 개수를 큐에 넣지 않는 식으로 시간 복잡도를 줄였다. 그렇게 했더니 정답을 출력할 수가 없었다..
전혀 감을 못 잡아서 다른 분들 코드를 봤더니 clipboard까지 고려해서 visited 배열을 2차원으로 하고 계셨다!

2차원으로 고치니 맞았습니다!

from collections import deque
import sys

input = sys.stdin.readline
goal_num = int(input())

current_num = 1
clipboard_num = 0
time = 0

dq = deque()
dq.append([current_num, clipboard_num, time])
visited = [[0] * 1001 for _ in range(1001)]
visited[1][0] = 1

while dq :
    fir = dq.popleft()
    current_num = fir[0]
    clipboard_num = fir[1]
    time = fir[2]

    if current_num == goal_num :
        print(time)
        exit()
    if 1000 >= current_num >= 0 and visited[current_num][current_num] == 0:
        dq.append([current_num, current_num, time + 1])
        visited[current_num][current_num] = 1
    if 1000 >= current_num + clipboard_num >= 0 and visited[current_num + clipboard_num][clipboard_num] == 0 :
        if current_num + clipboard_num == goal_num :
            print(time + 1)
            exit()
        else:
            dq.append([current_num + clipboard_num, clipboard_num, time + 1])
            visited[current_num + clipboard_num][clipboard_num] = 1
    if 1000 >= current_num - 1 > 0 and visited[current_num - 1][clipboard_num] == 0 :
        if current_num - 1 == goal_num :
            print(time + 1)
            exit()
        dq.append([current_num - 1, clipboard_num, time + 1])
        visited[current_num - 1][clipboard_num] = 1

13549번: 숨바꼭질 3

계속 이왜틀 시전하다가
반례 하나 보고 깨달음을 얻어서 해결했음.

0 3
2

X*2 해서 이동할 때 시간이 0초 걸린다는 걸 간과하고 풀었다..!

from collections import deque
import sys

input = sys.stdin.readline
n, k = list(map(int, input().split()))

oper3 = lambda x, y : [x + 1, y + 1]
oper2 = lambda x, y : [x - 1, y + 1]
oper1 = lambda x, y : [x * 2, y]

dq = deque()
dq.append([n, 0])

visited = [0] * 100001
visited[n] = 0

while dq :
    current, time = dq.popleft()
    if current == k :
        print(time)
        exit()
    for oper in [oper1, oper2, oper3] :
        n_current, n_time = oper(current, time)
        if 0 <= n_current <= 100000 and visited[n_current] == 0 :
            visited[n_current] = 1
            dq.append([n_current, n_time])

1261번: 알고스팟

참고 여부: O

우선순위가 있어서 arr이 0일 땐 앞쪽으로 넣는다는 아이디어를 떠올리지 못하고 있었다..
참고해서 성공!

import sys
from collections import deque

input = sys.stdin.readline
dq = deque()
dq.append([0, 0])

r = [-1, 1, 0, 0]
c = [0, 0, -1, 1]

col, row = list(map(int, input().split()))
arr = []
for _ in range(row) :
    arr.append(list(input())[:col:])

visited = [[-1] * col for _ in range(row)]
visited[0][0] = 0

while dq :
    cr, cc = dq.popleft()
    if cr == row - 1 and cc == col - 1 :
        print(visited[row - 1][col - 1])
    else :
        for i in range(4) :
            nr = cr + r[i]
            nc = cc + c[i]
            if 0 <= nr < row and 0 <= nc < col :
                if visited[nr][nc] == -1 :
                    if arr[nr][nc] == '1' :
                        visited[nr][nc] = visited[cr][cc] + 1
                        dq.append([nr, nc])
                    else :
                        visited[nr][nc] = visited[cr][cc]
                        dq.appendleft([nr, nc])