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로하고 수를 셀 때, 뱀이나 사다리에 도달하..

오늘 할 일 HttpServletResponse 사용법 익히기 HTTP 응답 메시지 생성 HTTP 응답코드 지정 Ex)200, 404, 400 등의 코드 헤더 생성 바디 생성 편의 기능 제공 Content-Type, 쿠키, Redirect 먼저 baisc 패키지에 response 패키지를 생성한다. 그 다음 응답코드 지정코드와 캐시 무효화 코드를 헤더에 설정한다. 추가적으로 사용자 생성 헤더 요소도 만들 수 있다. 한글 깨짐을 방지하기 위해서는 Content-Type에 charset = utf-8로 지정한다. //[status-line] response.setStatus(HttpServletResponse.SC_OK);//200정상응답 //[response-headers] response.setHeade..

오늘 할 일 HTTP 요청 데이터-API 메시지 바디를 활용하여 직접 바디 태그를 채워서 서버에게 데이터 요청하기 HTTP message body에 데이터를 직접 담아서 요청 HTTP API에서 주로 사용, JSON, XML, TEXT 데이터 형식은 주로 JSON 사용 POST, PUT, PATCH 먼저 가장 단순한 텍스트 메시지를 HTTP 메시지 바디에 담아서 전송하고, 읽어보자. HTTP 메시지 바디의 데이터를 InputStream을 사용해서 직접 읽을 수 있다. packagehello.servlet.basic.request; import org.springframework.util.StreamUtils; import javax.servlet.ServletException; import javax.s..

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는 여느때와 다름없이 큰틀은 똑같이 잡고 여기서 갯수를..