본문 바로가기

BFS

 (4)
[백준/Python] 14503 로봇청소기 전형적인 구현 문제이다. 문제에서 주어진 풀이 과정을 따라가며 풀면 된다. 방의 구조가 주어지고, 특정 위치에서 동서남북을 비교해가며 푸는 문제이므로 BFS를 활용해 구현했다. 반시계 방향으로 돌리는 걸 어떻게 구현해야할지 고민을 많이 했는데, 북(0)->서(3) / 서(3)->남(2) / 남(2)->동(1) / 동(1)->북(0) 임을 고려해 (d+3) % 4라는 식을 만들어냈다. N, M = map(int, input().split()) i, j, d = map(int, input().split()) room = [list(map(int, input().split())) for _ in range(N)] visited = [[0]*M for _ in range(N)] # 1. 현재 칸이 아직 청소되지..
[백준/Python] 11559 Puyo Puyo 문제를 보고 어떻게 구현할 지 생각을 하며 1. 같은 색 뿌요가 모여있는 걸 확인 2. 그 뿌요들을 터뜨리기 3. 중력 역할을 하는 장치 만들기 1~3의 작은 세 부분으로 나눴는데 이 중 제일 어려웠던 건 3번..이었다 1번은 상하좌우 비교하다가 같으면 또 그 자리에서 상하좌우 비교하고, 하는 걸 반복해야하므로 BFS를 사용해야겠다고 생각했고, 2번은 해당하는 자리를 다 '.'로 바꾸면 되니까 크게 어렵지 않을 것이라고 생각했는데, 3번은 도저히 어떻게 해야할지 생각하기가 어려웠다. 중력의 영향을 받는 건 상하 방향인데, 처음 필드를 입력받을 때 좌우 방향으로 리스트를 만들어서 받으니까 어떻게 구현해야할지 막막했다 찾은 해결 방법은 gameMap[3][0]에서 한 칸 떨어지면 gameMap[4][0]으로..
[백준/Python] 14502 연구소 2023.05.19 - [코테연습문제] - [백준/Python] 15686 치킨 배달 [백준/Python] 15686 치킨 배달 최대 M개를 고른다고 해서 처음에는 내가 최대 M개를 선택할 수 있다는 뜻인 줄 알고 그럼 1개, 2개, 3개,···M개 이렇게 다 나눠서 생각을 해야되는건가?! 하고 조금 많이 어렵게 생각했지만, 그게 sia-s.tistory.com 처음 문제를 봤을 때, 바로 BFS를 떠올린 건 아니다 처음 떠올렸던 생각은 저번에 풀었던 "치킨 배달"이 생각났다 치킨집과 집의 위치를 따로따로 저장해놓고, 치킨집을 N개 선택할 수 있는 모든 경우의 수를 조합으로 구해서 풀었던 문제였는데, 이 연구소 문제도 비슷한 방법으로 풀었다(대충 조합 썼다는 뜻ㅋㅋㅋ) 대충 내가 생각한 풀이법은 1. 바..
[백준/Python] 16234 인구 이동 예제4, 5를 이해하는 데에 시간이 좀 오래 걸렸다.. 아래는 이해한 예제4, 5를 정리해놓은 그림이다. 예제를 이해하고 코드를 작성하기 전에 했던 생각은, 1. 현재 국가(위치)를 기준으로 상하좌우 주변국들과의 인구수를 비교해야하니까 BFS를 사용하면 좋겠다 2. 그러면 인접한 나라들과의 인구수 비교를 해 연합국이 될 수 있는지를 확인할 수 있는 함수를 만들어야겠다 3. 연합국이 여러 개 일 수 있으니까, visited로 방문여부를 확인할 수 있어야겠다 4. 연합국들과의 인구조정이 된 후의 인구수로 상태를 계속 update해줘야겠다. 이정도였고, 코드를 작성하기 시작했다 from collections import deque dx = [0, 0, 1, -1] # 상하좌우 dy = [1, -1, 0, 0]..

티스토리툴바