내 인생 이대로 ㅈ될 수 없다

https://www.acmicpc.net/problem/7569

내 풀이

import sys
from collections import deque as dq

input = sys.stdin.readline

def solution():
    M,N,H = map(int,input().split())

    maps = [[list(map(int,input().split())) for _ in range(N)] for _ in range(H)]

    dx = [1,-1,0,0,0,0]
    dy = [0,0,1,-1,0,0]
    dz = [0,0,0,0,1,-1]
    q = dq()
    def bfs():
        
        while q:
            z,x,y= q.popleft()
            for i in range(6):
                nx = x + dx[i]
                ny = y + dy[i]
                nz = z + dz[i]
                if 0<=nx <N and 0<=ny <M and 0<=nz <H:
                    if maps[nz][nx][ny] == 0 :
                        maps[nz][nx][ny] = maps[z][x][y] + 1
                        q.append((nz,nx,ny))

    for i in range(H):
        for j in range(N):
            for k in range(M):
                if maps[i][j][k] == 1:
                    q.append((i,j,k))

    bfs()
    check = 0
    days = -2
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if maps[i][j][k] == 0:
                    check =1

                days = max(days,maps[i][j][k])

    if check ==1:
        print(-1) 
    elif days ==-1:
        print(0)
    else:
        print(days-1)



solution()

7576 번의 확장버전이다. 처음으로 z축이 붙은 문제를 풀어봤는데, 접근 자체는 같게 하면됐다. 

다른사람의 풀이

https://www.acmicpc.net/problem/7576

내 풀이

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

def solution():
    m,n = map(int,input().split())
    graph = [list(map(int,input().split())) for _ in range(n) ]

    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    def bfs():
        q = deque()
        for i in range(n):
            for j in range(m):
                if graph[i][j]==1:
                    q.append([i,j])
        while q:
            x,y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y+ dy[i]

                if 0<=nx<n and 0<=ny <m:
                    if graph[nx][ny] == 0:
                        q.append((nx,ny))
                        graph[nx][ny] = graph[x][y] + 1
    bfs()
    left_over = False
    max_days = -1
    for i in range(n):
        for j in range(m):
            if graph[i][j]==0:
                left_over = True
            max_days = max(max_days,graph[i][j])
    if left_over:
        print(-1)
    else:
        print(max_days-1)        

solution()

많이들 그랬을꺼같은데 N,M 가(로세로) 생각을 잘 해야한다. 아무생각없이 하면 틀린다.

다른사람의 풀이

https://www.acmicpc.net/problem/2606

내 풀이

1)BFS

import sys
from collections import deque

input = sys.stdin.readline

def solution():
    Num_Comp = int(input())
    Connect = int(input())
    graph=[[] for _ in range(Num_Comp+1)]
    visited = [False] * (Num_Comp+1)
    for _ in range(Connect):
        a, b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    count=0
    def bfs(virus):
        nonlocal count
        q = deque([virus])
        

        while q:
            v = q.popleft()
            
            visited[virus] = True

            for i in graph[v]:
                if visited[i] == False:
                    count +=1
                    visited[i]=True
                    q.append(i)

    bfs(1)

    print(count)

solution()

2)DFS

import sys
sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def solution():
    Num_Comp = int(input())
    Connect = int(input())
    graph=[[] for _ in range(Num_Comp+1)]
    visited = [False] * (Num_Comp+1)
    for _ in range(Connect):
        a, b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    count=0
    def dfs(virus):
        nonlocal count
        visited[virus] = True
        for g in graph[virus]:
            if visited[g] == 0:
                count +=1
                dfs(g)
    dfs(1)

    print(count)

solution()

결과론적으로 적어도 내 풀이로는 dfs로 푼게 bfs보다 메모리도 덜 먹고 시간도 덜 걸렸다.

dfs의 단점은 잘못 걸릴경우 속도가 너무 오래걸린다는것인데, 위 문제처럼 큰 깊이가 필요없는 경우에는 당연히 dfs가 더 빠르다. 적어도 지금까지 내가 풀어 본 문제들은 모두 bfs,dfs 둘 다 적용 가능한 경우가 대부분이였는데, 그렇기에 두개 다 풀이 방법을 아는것이 중요한거 같다.

다른사람의 풀이

_,_,*i=open(0)
for _ in(n:=[-1,1]+[0]*99):
 for l in i:a,b=map(int,l.split());n[b]=n[a]=n[a]|n[b]
print(sum(n))

뭐..할말이없다 ㅋㅋ 

https://www.acmicpc.net/problem/24445

내 풀이

앞서 풀었던 dfs의 bfs버전이다. 

다른사람의 풀이

https://www.acmicpc.net/problem/24479

내 풀이

배워갈게 많은 문제라고 생각한다.

sys.setrecursionlimit(10 ** 8) 

코딩 테스트 중 dfs 문제를 처음 볼 때 흔히 걸리는 런타임 에러를 잡기 위한 필수적인 라인이다.

파이썬의 기본 재귀 제한은 상당히 작은편이다. dfs 문제를 파이썬으로 풀때는 무조건, 무조건 쓰고 시작해야한다.

이번 풀이하면서 좀 헷갈렸던게 nonlocal과 global이다.

이번 풀이로 확실하게 배웠다.

전역변수를 활용할때는 global

지역변수를 활용할때는  nonlocal

다른사람의 풀이

https://www.acmicpc.net/problem/18352

내 풀이

from collections import deque
import sys

input = sys.stdin.readline

N,M,K,X = map(int,input().split())
graph=[[] for _ in range(N+1)]
distance = [-1] * (N+1)
distance[X] = 0

for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)




q = deque([X])

while q:
    now = q.popleft()
    for next in graph[now]:
        if distance[next]==-1:
            distance[next] = distance[now] + 1
            q.append(next)

check = False

for i in range(1,N+1):
    if distance[i] == K:
        print(i)
        check=True

if check == False:
    print(-1)

이 문제의 핵심은 모든 간선의 비용이 1이라는 점이다. BFS는 모든 간선의 비용이 1일 때만 사용가능하다.

그래프에서 N이 아니라 N+1을 받은 이유는 1부터 시작한다는 점에서 직관성을 높여주려고 1부터 N까지 이용하였다.

애초에 1부터 차례차례로 확인하기 때문에 정렬이 필요없다.

참고로 그냥 input()으로 받으면 시간초과난다.

다른사람의 풀이

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

n, m, k, x = map(int, f().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, f().split())
    graph[a].append(b)

def bfs(start):
    answer = []
    q = deque([start])
    visited[start] = True
    distance[start] = 0
    while q:
        now = q.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = True
                q.append(i)
                distance[i] = distance[now] + 1
                if distance[i] == k:
                    answer.append(i)
    if len(answer) == 0:
        print(-1)
    else:
        answer.sort()
        for i in answer:
            print(i, end='\n')

bfs(x)