문제https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의www.acmicpc.net 접근법처음에 BFS로 풀면 되겠다 싶어 BFS로 풀어 통과를 했다. 그런데 채점현황을 보니 나만 메모리랑 시간이 장난아니게 컸다.. 심지어 처음에는 시간초과가 발생했다. 그래서 알고리즘 분류를 봤더니 DP를 사용하는 문제였다..!ㅋㅋ 두 풀이 다 설명해보겠다. BFSPipe 클래스를 하나 만들어 파이프가 시작하는 위치, 파이프의 방향을 변수로 가지도록 하였다. 그냥 BFS..
문제https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기첫째 줄에 방의 크기 N과 M이 입력된다. (3≤N,M≤50) 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (r,c)와 처음에 로봇 청소기가 바라보는 방향 d가 입력된다. d가 0인 경우 북쪽www.acmicpc.net 접근법쉬운 구현 문제이다. 동서남북~ 에서 BFS를 사용하라는 것을 대놓고 보여준다. 문제에서 주는 작동 방식을 정말 그.대.로 구현하면 된다. 주의할 점은 방향을 다루는 것인데 문제에서 제시한 방향은 0북 1동 2남 3서 이지만 반시계 방향으로 회전하는 것은 북->서->남->동 이기 때문에 잘 처리해주어야 한다. 나 같은 경우 dir 배열을 0..
문제https://www.acmicpc.net/problem/16236 16236번: 아기 상어N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가www.acmicpc.net 접근법최단 거리를 구하는 문제이기 때문에 BFS를 사용한다. 알고리즘먹을 수 있는 물고기가 남아있을 때까지 BFS를 반복해서 수행한다. 보통은 boolean[][] visited 배열을 사용해 방문 여부를 표시하지만, 나는 물고기를 먹으러 가는데 얼마나 걸리는지를 계산하기 위해 int[][] count를 사용해 해당 지점까지 얼마나 걸리는지를 나타내었다. BFS를 탐색을 하면서 아기 상어가..
