[SWEA] 구슬탈출 2
문제조건 빨간구슬, 파란구슬 두 개가 동시에 위치 이동을 한다. (정점의 위치가 변한다!) 빨간구슬, 파란구슬은 같은 위치에 있을 수 없다. (장애물정점의 위치도 변한다!) 한 번 이동 시, 갈 수 있을 때까지 쭈욱 간다. 핵심개념 BFS에서 queue에는 x,y 좌표 한 개만 담으라는 법은 없다. 빨간구슬의 (x,y), 파란구슬의 (x,y)를 같이 담는다. 종료조건을 먼저 생각하자. 1) 움직인 횟수 10번 넘었거나 (실패) 2) 10번 안 넘었지만 탈출할 수 없거나 (실패) 3) 빨간구슬이 탈출에 성공했거나 코드 from collections import deque n, m = map(int, input().split()) a = [list(map(str, input())) for _ in range..
2019. 10. 9.
[BOJ1261 알고스팟] BFS (Python)
문제조건 벽이 있으면 뚫고 이동, 벽이 없으면 그냥 이동한다. 핵심개념 가중치(부수는 벽의 개수)는 벽이 있느냐 마느냐에 따라 0이거나 1이다. 가중치가 1이면 deque의 왼쪽, 0이면 deque의 오른쪽을 사용한다. (2개의 큐인 것처럼 활용) 코드 from collections import deque n, m = map(int, input().split()) miro = [list(map(int, input())) for _ in range(m)] check = [[False] * n for _ in range(m)] dist = [[-1] * n for _ in range(m)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 처음 위치 q = deque() q.append..
2019. 10. 7.
[BOJ3055 탈출] BFS (python)
문제조건 물은 1분이 지날 때마다 인접한 곳에 물이 찬다. 단, 돌이거나 비버의 소굴은 물이 차지 않는다. 고슴도치는 물과 돌은 못 간다. 핵심개념 물 차는 시간을 미리 구해놓는다. (토마토 문제 방법으로 구하면 된다.) 위, 아래, 왼쪽, 오른쪽 인접한 곳을 탐색한다. 코드 from collections import deque n, m = map(int, input().split()) a = [list(map(str, input())) for _ in range(n)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 물 차는 시간 먼저 구하기 (토마토 문제랑 동일) # 구하는 김에 고슴도치랑 비버의굴 위치도 구하기 water = [[-1] * m for _ in range(n)]..
2019. 10. 7.