dfs 썸네일형 리스트형 [백준] 22352 항체 인식 / 자바(Java) 문제 https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 해설 문제에 나오는 CPCU-1202 백신은 2차원 배열 중 단 한곳에 떨어지고, 그 떨어진 곳과 인접하며 같은 숫자인 위치로 퍼지며 모두 퍼지게 된 이후에 함께 어떤 특정 값으로 바뀌는 특징이 있습니다. 문제의 입력값은 2차원 배열의 이전 모습과 이후 모습을 주며 해당 백신이 들어갔을 가능성이 있는가를 파악하는 것이 문제입니다. 문제의 풀이방식은 .. 더보기 [백준] 2239 스도쿠 / 자바(Java) 문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 해설 스도쿠를 해본 분이라면 상상만 했던 스도쿠를 자동으로 푸는 코드를 짜는 문제입니다. 구현문제로 큰 어려움 없이 필요한 동작들을 순서대로 실행하면 가능합니다. 1. 빈칸들을 확인하기 2. 빈칸에 들어갈 수 있는 수를 하나씩 넣어보기 3. 다음 빈칸을 확인하기 4. 2와3을 반복하며 모든 빈칸에 옳은 값을 넣은 경우 반복종료 사람과는 달리 컴퓨터는 예측이 아닌 모든 수를 넣고 가능한 .. 더보기 [백준] 1987 알파벳 / 자바(Java) 문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 해설 2차원배열에서 4방탐색을 통해 가장 많이 가는 횟수 찾기 문제입니다. 특이한 점은 다른 문제처럼 숫자가 아닌 알파벳으로 2차원 배열이 구성되어있고, 특정 위치의 방문여부가 아닌 특정 알파벳을 방문했는가에 따라 추가탐색의 가능 여부가 갈립니다. 문자열이 아닌 알파벳의 방문여부이기 때문에 map을 사용하지 않고 26까지 있는 1차원 배열을 통해 index 0의 값은 A, ind.. 더보기 [백준] 1937 욕심쟁이 판다 / 자바(Java) 문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 해설 판다가 돌아다닐 수 있는 가장 많은 칸을 찾는 문제입니다. 출발점이 정해져 있지 않으니 모든 점을 출발점으로 경로를 확인해야 합니다. 지나온 값의 총 합의 기반으로 경로를 정하지 않기 때문에 2차원 dp배열을 통해 연산량을 줄입니다. dp[i][j]는 (i,j) 위치를 지날 때 가장 많이 이동한 횟수 dfs를 통해 지도의 모든 위치에서 주변 4방을 탐색 후 자신보다 큰 위치(.. 더보기 [백준] 3109 빵집 / 자바(Java) 문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 해설 주어진 2차원 배열에서 1열과 마지막 열을 잇는 줄을 겹치지 않고 얼마나 많이 만들 수 있는가에 대한 문제입니다. 가장 많은 줄을 만들기 위해서 가장 위의 행부터 시작해 가능한 한 위쪽으로 줄을 만드는게 효율적이라 판단하는 그리디 방식을 통해 해결합니다. DFS를 통해 가장 위쪽을 통해 넘어가는 줄을 만들고 진행 여부를 2차원 배열에 표시해 해당 위치로 중복해서 넘어가지 않도록 지정해줍니다. 또한 중간.. 더보기 [프로그래머스] 광물 캐기 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/172927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 작업이 끝날때의 최소 피로도를 구하는 문제입니다. 광물을 순서대로 캐야하며, 광물의 순서에 규칙이 있는 것이 아니여서 완전탐색이 필요합니다. 또한 모든 가지수를 대입할 때 최대 광물의 수 50, 곡괭이는 각각 5개씩이므로 각 곡괭이의 선택 경우의수는 3의 10제곱정도라 시간, 공간 복잡도에 무리가 가지 않고 문제를 해결할 수 있습니다. arr 이차원 배열을 통해 [곡괭이][광물] 인 .. 더보기 [프로그래머스] 피로도 / 자바(Java) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 각 던전을 확인하는데 소모 피로도와 현재 피로도의 차이, 최소 필요 피로도 2가지를 비교해야하기 때문에 완전탐색으로 모두 확인해보아야 합니다. 따라서 완전 탐색 중 dfs를 이용해서 해결했습니다. 방문여부를 확인할 배열 visited[], 가장 많이 돈 던전 수를 확인할 answer를 외부에 저장해 줍니다. 이후 dfs를 구성해 줍니다. public void dfs(int count, .. 더보기 이전 1 다음
