본문 바로가기

알고리즘

 (151)
[JAVA]BOJ(백준) - 벽 부수고 이동하기 - 2206 문제 내용 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 최단거리를 찾는 BFS에 벽을 한번 부수고 지나갈 수 있는 조건이 추가된 문제이다. 문제 접근 방법 첫번째로 생각한 방법. BFS를 돌리는데 벽의 존재 여부에 따라 경우의수가 나뉜다는 생각을해서 벽을 처음 만날때마다 백트래킹으로 옳은길인지 아닌지를 하나씩 판단해야겠다 라는 생각을 했다. 그리고 문제에서 입력으로 주어진 2차원 배열 map의 요소값을 1씩 증가시키..
[JAVA]BOJ(백준) - 숨바꼭질 - 1697 - 문제 내용 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net - 문제 접근 방법 개인적으로 너무너무 아쉬운 문제다... 알고리즘 문제 풀때 1~2시간 고민하고 답안보이면 다른 분들 풀이를 참고하는 편인데 이건 내능력으로 충분히 풀수 있는 문젠데 생각하지 못해서 다풀지 못한문제다..ㅠ 문제를 풀기위해 가장먼저 생각한건 수빈(N)의 위치와 동생(K)의 위치가 처음부터 같다면 0을 출력. 만약 수빈이의 위치가 동생 위치보..
[JVAV] BOJ(백준) - 토마토 - 7569 - 문제 내용 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net - 문제 접근 방법 이문제는 전에 풀었던 토마토(7576) 문제와 그냥 똑같은 풀이방법으로 푼다고 생각하면된다. 하나 다른점은 토마토박스가 3차원배열로 돼있고 상하좌우 뿐만아니라 위아래의 경우도 생각해야 한다는점만 다르다. 이말은 토마토박스를 3차원 배열로 받고 위아래 경우를 어떻게 처리할지만 알면 바로 풀수 있다는 말이다. 위아래의 경우는 단순히 상하좌우처럼..
[JAVA] BOJ(백준) - 토마토 - 7576 - 문제 내용 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net - 문제 접근 방법 익은 토마토 기준으로 상하좌우에 있는 익지 않은 토마토들이 하루가 지날때마다 익어가는 문제이므로 상하좌우의 토마토가 0인지 판단만 해준다면 풀수 있는 문제라고 생각했다. 그리고 주의할점은 처음에 익은 토마토는 여러개가 있을 수도 있어서 동시다발적으로 익어가는 상황도 고려해야한다는 점이다. 그래서 처음에 큐에는 익은 모든 토마토들의 행과 열의 위치값..
[JAVA]프로그래머스 - 단어 변환 - 문제 내용 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr - 문제 접근 방법 문제를 읽어보면 begin단어에서 target단어로 되기까지 과정이 탐색한 단어와 begin 단어는 한글자 빼고 모두 같은걸 알수 있다. 그리고 단어의 스펠링이 바뀔수 있는 모든 경우의수를 하나씩찾고 아니면 되돌아와서 다른 스펠링을 바꿔서 다시 찾고 해야한다. 그래서 해당문제는 백트래킹..
[JAVA]BOJ(백준) - 미로 탐색 - 2178 - 문제 내용 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net - 문제 접근 방법 가장먼저 모두 탐색하는 것이 아니라 최소의 칸수 즉, 최단 거리를 구하는 문제라 BFS 방식을 쓰는것으로 생각했다. 그리고 다른 DFS 문제와 마찬가지로 상하좌우를 탐색하는데 인접한 모든 값들을 살핀다. 또 미로의 값을 하나씩 탐색할때마다 이전값+1을 해줌으로써 한단계씩 넘어갈 때 마다 값을 증가시킨다. 가장 시간이 많이 걸렸던 점은 그래프의 경우 노드를 큐에 넣고 빼고를 반복하면 되는데 이건 ..
[JAVA]BOJ(백준) - 유기농 배추 - 1012 - 문제 내용 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net - 문제 접근 방법 가장 먼저 집단화된 배추들의 개수를 알수있다면 배추벌레의 수도 알 수 있다. 그래서 단지번호붙이기(2667)처럼 집단 하나하나를 dfs로 세다보면 답이나온다. 필요한 것들 -> 방문배열, 배추맵, 벌레수 세주는 변수, count한 벌레 넣을 리스트, 상하좌우 배열 여튼 단지번호붙이기(2667) 문제와 비슷데 이문제가 더 간단하다고 생각하고 입력값에 대해 어떻게 함수를 어떻게 ..
[JAVA]BOJ(백준) - 단지번호붙이기 - 2667 - 문제 내용 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net - 문제 접근 방법 입력받은 값을 2차원배열에 넣어 하나씩 0인지 1인지를 확인하기 2차원배열의 방문배열을 만들어서 방문여부도 함께 확인하기 확인된 집으로부터 dfs로 상하좌우를 돌면서 집이 있는지 없는지 확인하기 집이 없다면 해당 dfs를 끝낸다. 집이 있다면 다음 dfs를 호출한다. 이렇게 문제를 접근하면서 필요한것들 -> 집세주는 변수, 단지수 알려주는 변수, 방문배열 까지는 생..

티스토리툴바