DFS

16166 백준 파이썬

오랜만의 DFS 무엇을 리스트와 딕셔너리에 저장할지 고민하는데 시간이 많이 걸렸다. 중요한 건 " 환승 "이다. 따라서 환승 못하는 역들에 대해서는 굳이 dfs연산을 할 필요가 없다. 환승 할 수 있는 것들은 h[x]의 길이가 2보다 크다. 이것들에 대해서만 dfs연산을 진행했다. def dfs(start, dest,cnt): havetogo=[] for x in route[start]: if x==dest: return cnt if len(h[x])==1 and x not in vis: #환승 못하는 것들 vis.append(x) else: if x not in vis: vis.append(x) havetogo.append(x) for x in havetogo: return dfs(x, dest,cnt..

1043 백준 파이썬

DFS로 해결했다. p라는 리스트에 진실을 아는 사람 번호를 넣는다. stack에 p리스트를 복사해서 넣는다. p배열에 있는 값들의 vis값을 1로 바꿔주고, stack에서 하나씩 꺼내어 party 리스트의 한줄씩 골라 비교한다. 비교했을때, party 리스트의 한 줄 안에 stack에서 꺼낸 값이 있으면, stack에 party리스트 안의 값(r)을 추가하고, p리스트에도 추가한 뒤에 vis[r]=1한다. 이렇게 되면 마지막에는 p값에 파티를 통해 진실을 알게된 모든 사람이 담기게 된다. 이를 다시 한번 party리스트와 비교하여 되는 리스트만 뽑아주면 되겠다. n,m=map(int,input().split()) p=list(map(int,input().split())) party=[] for x in..

17070 백준 파이썬

어떤 문제든, 문제를 잘 읽는게 제일 중요하다. 문제를 제대로 안읽어서 BFS로 접근했던 문제 가로, 세로 상황에서 대각선으로 꺾는것을 기준점의 이동 없이 옮기는 줄 알고 여러가지 가능한 경우 중 최단거리의 갯수를 찾는 문제인 줄 알았다. 하지만 이건 DFS이다. 다중 조건 미로찾기라고 생각하면 될 것 같다. 기준점과 움직이는 점을 분리해서 푼 코드이다. import sys input=sys.stdin.readline def bfs(stdx,stdy,mvx,mvy): if mvx==n-1 and mvy==n-1: global c c+=1 return #가로 if stdx==mvx and stdy==mvy-1: if mvy+1

1504 백준 파이썬

다익스트라 알고리즘에 대한 정확한 이해가 없어서 어려웠던 문제. 이 문제를 통해서 개념을 확실히 익혔다. 다익스트라는 dfs와 비슷한 방식으로 작동한다. 최단 경로는 최단 경로의 합이라는 알고리즘으로 작동한다. 따라서 힙을 통해 구현할 수 있다. 약간 조건이 잔뜩붙은 dfs같은 느낌이다. 시작점에서 최단경로를 찾는다 -> 최단경로를 힙에 넣는다 -> 최단경로를 꺼내어 시작점과 중간 경로까지의 값과 비교한 후에 최단 경로가 더 짧은 경우에만 더 진행한다.(이걸로 시간초과가 갈린다.) -> 현재 저장된 중간경로에서 또 다른 경유 지점까지의 합이 저장된 거리보다 짧을 경우, 저장된 거리를 갱신한다. -> 저장된 거리를 힙에 다시 넣는다. 그리고 이 문제의 경우, 특정한 경로를 지나야 하는데 그 발상을 떠올리지..

2206 백준 파이썬

오랜만의 bfs, dfs 항상 그렇듯, dfs는 시간초과다. 처음 짠 코드 from collections import deque import sys input=sys.stdin.readline n,m=map(int,input().split()) M=[] for _ in range(n): M.append(list(str(input()))) def bfs(x,y,Mcopy): vismap=[[0 for x in range(m)] for y in range(n)] q=deque() cnt=1 q.append([x,y,cnt]) while q: x,y,cnt=q.popleft() a=[-1,1,0,0] b=[0,0,-1,1] for t in range(4): X=x+a[t] Y=y+b[t] if 0

BFS, DFS 스페샬 (백준 1012, 2178, 1389, 1697)

이전 게시글에서 BFS와 DFS에 대해 다뤘었다. 이번에는 그 응용. 첫번째는 1012번이다. 말이 어렵지 그냥 1 연속된 칸의 갯수를 구하는 문제다. (x,y)의 값만 잘 설정한 뒤에는 dfs든 bfs든 상관없이 풀이해도 된다. t=int(input()) for _ in range(t): stack=[] li=[] cnt=0 x1=[1,-1,0,0] x2=[0,0,1,-1] m,n,k=map(int, input().split()) space=[[0]*n for x in range(m)] check=[[0]*n for x in range(m)] for _ in range(k): a,b=map(int, input().split()) space[a][b]=1 li.append([a,b]) for x in r..

탐색 알고리즘 -dfs와 bfs (백준 1260)

그들과의 첫 조우 - 백준 1260번 이번 문제, 푸는데 20시간은 걸린거 같다. 그만큼 몰랐던 개념이 많았던 문제고 그에따라 많은 개념을 익혔다. 일단 문제를 풀며 가장 난이도를 느낀 부분이 그래프의 구현이었다. 나는 애초에 그래프가 뭔지도 몰랐다. 그리고 스택과 큐 역시 전공수업을 들으며 대충은 개념을 알고 있었지만, 실제로 써본 것은 처음이었다. 1. 그래프 그래프란 정점과 간선으로 이뤄진 자료구조다. 정확하게는 정점사이의 관계를 나타낸 자료다. 자 이걸 어떻게 프로그램한테 설명할 것인가? 크게 두가지 방법으로 표현 할 수 있다. 1) 인접 행렬 정점의 수에 따라 n*n의 2차원 리스트를 생성한뒤, 그 내용을 0으로 채워넣는다. 그 후에 1,2라는 정점사이에 간선이 존재한다면 arr[1][2]=1,..