BFS28 [BOJ] 6087. 레이저 통신(Python) / BFS www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 연속으로 BFS 최단거리 문제를 풀었다. 문제를 처음 접했을 때 이전의 로봇 문제처럼 맵을 방향별로 만들어줘야겠다는 생각을 했는데, 조금 더 생각해보니 그렇게까지 할 필요는 없을 것 같고, 머릿 속으로 BFS 이차원 맵을 어떻게 채울지 생각했다. 초기 check 맵을 최댓값 float('inf')으로 채워 놓는다. 시작 위치에서 4방향으로 쭉쭉 직진으로 벽이나 격자 밖으로 나갈 때까지 그려주고, 그 다.. 2021. 3. 22. [BOJ] 1726. 로봇(Python) / BFS www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net BFS 최단거리 문제다. 처음에 문제 봤을 때 어떻게 풀어야할지 좀 막막했는데 여러 솔루션들을 보고 아이디어를 얻었고, 특히, 뚱이가 코드를 보내줘서 완벽히 이해할 수 있었다. 내 스타일대로 다시 풀어봤다. 이 문제에서 포인트는 visited를 맵의 크기대로 그리되, 각 위치별로 4방향(동서남북) 정보를 담을 수 있도록 * 4 해주는 것! 큐에 위치와 방향, 그리고 cnt값을 담았다. 해당 정보를 visited에 표시하며.. 2021. 3. 22. [BOJ] 3055. 탈출(Python) / BFS www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net # 59분 소요 골드 5 난이도로, 무난한 BFS 문제였다. input 받으면서 고슴도치의 좌표와 물의 좌표를 각각의 큐에 저장, 물과 고슴도치 visited의 해당 위치를 0으로 표시 물의 이동을 wbfs() 함수로 도달할 수 있는 거리 표시(water) 고슴도치의 이동을 hbfs() 함수로 갈 수 있는 곳으로 퍼트린다(hedgehog) 이동 중 비버의 집(D)를 만나면 거리 출력하고 종료 다 퍼트렸는데 비버의 집에 도달.. 2021. 3. 12. [BOJ] 2206. 벽 부수고 이동하기(Python) / BFS www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 꽤 고차원적인 BFS 문제이다. 이 문제 사실 4번째 푸는 문제더라.. 그 와중에 1시간 반 정도 걸려서 풀었다, 인풋부터 잘못 받아서 계속 틀렸다. int가 아니라 str로 받아서 자꾸 BFS를 퍼트리지 못했다ㅠㅠ bfs 함수 안에서 꽤 헤맸다. 폭탄 가지고 있을 때, 없을 때를 다른 visited에 표현 큐에 폭탄(벽 부술 기회) 정보와 위치 정보를 담으면서 BFS 퍼트리는 것이 핵.. 2021. 3. 7. [SWEA] 5644. 무선 충전(Python) / BFS + Simulation swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성 모의 SW역량테스트 문제 중 어느정도 난이도가 있는 문제에 속한다. 1시간 37분 소요. BFS + Simulation BFS로 각 BC의 충전 범위를 그려줌(다음에 풀 때는 BFS 안 쓰고 위치의 절대값으로 BC의 범위를 그려보자) 핵심은 두 개 이상의 BC의 범위가 겹칠 때, 성능이 큰 순으로 내림차순 정렬하는 것. 이동할 때, 시작 위치도 포함해야 함. 가장 까다로운 부분은 두 사람이 같은 BC에 있는.. 2021. 3. 7. [BOJ] 2583. 영역 구하기(Python) / BFS www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net # 22분 소요 아주 간단한 BFS 문제 M*N크기 맵 1로 초기화 Input 받은 내용을 미리 M*N크기의 맵에 0으로 그려줌 이후 맵에서 1일 때 연결된 곳 BFS 이용하여 0으로 지워주면서 갯수 셈 연결된 곳 0으로 지우는 작업 끝날 때마다 resut += 1, parts에는 갯수 append 해주고, 마지막 출력할 때 sort 파이썬 코드는 다음과 같다. import sys input.. 2021. 3. 4. 이전 1 2 3 4 5 다음
