BFS

백준 17070번: 파이프 옮기기 1 (파이썬, DFS, DP)

멘탈이 나간 문제이다. 골드V에서 이정도로 헤멘건 처음이다.. 삼성 A형 기출문제중 하나인데 2차원 배열이 주어지길래 당연히 dfs, bfs로 접근하려 했다. 나는 bfs로 접근하였는데 파이프가 가로인지, 세로인지, 대각선인지 판단을 해야해서 queue에 두 점의 좌표를 튜플과 리스트로 감싸 넣었다. 대각선일땐 세점이 방문 불가하고 파이프의 왼쪽은 파이프가 옮겨질 때 옮겨지기 전 파이프 오른쪽의 좌표로 옮겨진다는 두 포인트를 잡고 코드를 짰다. import sys from collections import deque def bfs(n): global cnt queue = deque(n) while queue: now = queue.popleft() if now[0][0] - now[1][0] == 0: ..

백준 2667번: 단지번호 붙이기 (파이썬, BFS)

BFS로 푸는 문제이다. 아파트가 있는곳은 1, 아파트가 없는곳은 0으로 표시되기 때문에(이진법) 방문여부를 확인하는 배열을 따로 만들지 않고 방문 시 배열값을 0으로 함으로써 다시 방문할 일이 없게 하였다. 근소한 차이긴 하지만 실행시간을 약간이라도 줄이는 것을 확인하였다. import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(x, y): global cnt graph[x][y] = 0 q = deque([(x, y)]) while q: now = q.popleft() for i in range(4): nx = now[0] + dx[i] ny = now[1] + dy[i] if 0

백준 7576번: 토마토 (파이썬, BFS)

개인적으로 좀 어려웠던 문제였다. 왜냐하면 쉬운 BFS문제들은 보통 탐색을 한 회 할 때마다 카운트를 늘리면 되는데, 이 문제는 한 계층을 다 탐색한후에 카운트를 늘려야 했기 때문이다. 왜냐하면 1초가 지날때, 익은 토마토 주변의 토마토들이 모두 익기때문이다. 따라서 1초마다 익은 토마토 주변의 모든 토마토가 익는다는것을 구현하기 위해 입력받은 값에서 값이 1인 값들을 새로운 배열에 저장하고, 그 배열을 BFS의 입력으로 썼다. 그리고 while문 안에도 빈 배열을 선언하였는데, 입력받은 값들 중 값이 1인값들 주변을 탐색하였을 때 1초후에 값이 1이 되는 값들(0)을 배열에 모아 덱에 저장하기 위함이다. 이렇게 덱에 있는 원소(배열)를 다 탐색한 후에 카운트를 늘리면 통과한다. 또한 모두 익지는 못했을..