https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 오늘 풀어본 문제는 여지껏 해왔던 BFS문제와는 조금 다르다. 다른 문제들과 다른점이 무엇인가 하면 방문처리의 배열이 다르다. 지금까지는 1차원 또는 2차원 배열로 방문처리를 해왔다. 하지만 이 문제는 3차원 배열로 처리해야한다.(물론 토마토 문제의 경우 3차원이 있었다. 하지만 이 문제의 3차원 배열은 좀 다르다.) 문제의 내용은 벽을 딱 한번 부술 수 있고, (1,1)..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제는 1에서 시작해서 100에 도달하는 방법을 주사위가 나오는 눈의 수로 했을 때 최단으로 가는 걸 구하는 문제다. 여기서 신경 쓸것은 뱀과 사다리이다. 기본적으로는 주사위의 눈의 수만큼 이동하지만 사다리나 뱀을 만나면 그 위치로 이동하게 된다. 처음 이 문제를 풀때 헷갈리는 부분이 있었다. 시작점을 1로하고 수를 셀 때, 뱀이나 사다리에 도달하..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이번 문제는 접근을 아예 못할 것은 아니였지만 접근 과정에서 N,M을 정하는게 헷갈리고, 동시에 여러 곳에서 탐색이 진행되야 한다는 것에서 구현을 하는 것에 어려움이 있었다. 그래서 결국 질문 게시판에서 다른 사람들의 접근 방식을 봐버렸다... 이 문제의 접근 방법은 다음과 같다. 일단 익어있는 모든 토마토의 좌표를 큐에 집어넣어서 탐색을 시작하는 것이다. 그렇게 되면 동시에 탐색..
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 이번 문제는 knight의 이동 문제이다. 말그대로 체크판에서 하나의 시작점에서 도착지점으로 이동하는 최소 횟수를 구하는 것이다. 즉, 나이트가 이동하는 방향은 8방향이 있다. 그림으로 나타내면 문제의 주어진 아래의 그림과 같다. 그리고 이걸 x,y 좌표로 나타내면 아래와 같이 나타낼 수 있다. int[] dx = {1, 2, 2, 1,-1,-2,-2,-1}; int[] dy = {2, 1,-1,-..
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이번 문제는 가장 적은 시간. 즉, 최소시간을 구하는 문제였다. 최소 시간을 구하기 위해서는 BFS가 제일 적합하다고 생각했다. 문제의 분류 또한 그렇게 나와 있었다. DFS로 하기에는 최소를 구할 수 있다는 보장이 부족하고, 하나, 하나의 탐색 시간이 아주 오래걸릴 확률이 있기 때문에, BFS로 풀었다. 원리는 BFS의 큰 틀에 조금의 조건을 부합시켰다. 조건은 일단 ..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 문제는 DFS로 풀려고 노력해봤지만 못풀었다.. 원인은 문제의 예제 마지막에 주어진 원순회가 있는 예제 때문이다. 백트래킹 방식으로 구현을 하였는데 이 과정에서 원순회를 만나면 무한 순회를 돌아서 stackoverflow가 떠버린다.. 혹시 DFS로 풀 해결책을 알고 있는 분이 있다면 한 수 가르쳐 주시면 좋겠다.. 그래서 방법을 바꾸어 BFS로 해결책을 돌렸다. BFS는 여느때와 다름없이 큰틀은 똑같이 잡고 여기서 갯수를..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 2667번과 거의 동일하다. 다른 점이라면 테스트 케이스를 입력 받은만큼 실행한다는 것과, 배추가 있는 좌표를 찍어야 한다는 점 정도이다. 나머지는 2667번과 동일하게 DFS,BFS 모두로 풀 수 있을 것이다. 풀이 방법은 먼저 테스트 케이스를 몇 개 실행할지 입력 받는다. 그 다음에 가로 길이 M과 세로 길이 N을 입력 받고 배추의 갯수인 K를 입력받는다. 그 다음 아래 K개의 줄에 배추가 있는..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이 문제는 조금 헷갈리는 부분이 있었다. 1인 부분에 대해서 탐색을 모두 해야하는데 그걸 어떤식으로 해서 반복해야하는지 막막한 부분이 있었는데, 질문 게시판에서 그에 대한 해결책을 얻었다. 방법은 주어진 단지 테이블에서 각각의 위치마다 1인것에 대해 DFS나 BFS를 통해 탐색을 진행하는 방식으로 하면 된다는 것을 알았다. 즉, 단지 테이블에 1인 지점이 나오면 이에 대해 탐색을 진행하고, 탐색이 ..
