본문 바로가기

Algorithm/BFS & DFS9

[백준] 4179번 : 불! https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 지훈이가 미로를 통과할때 or 통과하지 못하는 경우를 위한 탈출 조건만 유의해주자! 처음에는 bfs함수로 두지않고 main에서 로직을 처리하고 bool 변수를 통해 종료조건을 걸어주려고 했지만, 고려하지 못한 상황이 있었는지 틀렸다고 한다. 따라서, 함수로 따로 두고 종료시점에 바로 return cnt를 통해 해결하였다. #include #include using namespace .. 2021. 11. 23.
[프로그래머스] 코딩테스트 고득점 Kit - BFS/DFS (JAVA) https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr class Solution { int answer=0; int total=0; public void dfs(int[] n, int sum,int cnt){ if(cnt==n.length){ if(sum==total) answer++; return; } dfs(n,sum+n[cnt],cnt+1); dfs(n,s.. 2021. 10. 1.
[프로그래머스] 거리두기 확인하기 (C++) (2021 카카오 채용연계형 인턴십) https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 2021 카카오 채용연계형 인턴십 코테에서 직접 풀었던 문제이다. 그때도 이 문제는 해결했.. 2021. 9. 11.
[프로그래머스] JetBrains x 프로그래머스 월간 코드 챌린지 본격적인 코테 치기전 몸풀기로 JetBrains x 프로그래머스를 지원해보았다. 총 4문제중 2문제를 맞혔다. 3,4번은 문제 읽자마자 풀 수 없을 것같아서, 2번까지만 풀고 그냥 나왔다. 1번은 단순 구현이었기에 패스하고, 2번만 코드를 남겨본다! 2번문제는 주어진 맵에서 발생하는 모든 사이클의 대한 길이를 출력하는 문제였다. 각각의 경로마다 특징이 있었기에 DFS로 풀어야겠다고 생각했고, 동서남북 4가지 방향에 대한 방문 체크를 위해 3차원 DFS로 구현하였다. 분명 틀린게 없는게 자꾸 틀렸습니다가 뜨길래, 다시 문제를 읽어보니 출력시 오름차순 조건을 빼먹었었다. 이것때문에 거의 30분을 날려먹었다..... 허무하다 문제 조건을 꼼꼼히 확인하자 제발!! 전체 코드는 아래와같다. #include #in.. 2021. 9. 9.
[프로그래머스] 게임맵 최단거리 (C++, JAVA) https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 레벨 : Level 2 전형적인 bfs문제로 추가설명은 생략 :) #include #include #include using namespace std; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int visit[100][100]; //bfs int solut.. 2021. 9. 8.
[백준] 1600번 : 말이 되고픈 원숭이 (C++) https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 최단 거리를 구하는 문제이기 때문에 BFS로 구현하였다. 평소 하던대로 BFS 구현은 금방하였지만, 메모리초과 문제가 떠버렸다. 보통 bfs문제에서는 한번 방문한 곳은 지나가지 않도록 로직을 구현했지만, 이 문제에서는 경우에 따라 방문했던 곳이더라도 나이트의 이동 수에 따라 정답 경로가 될수 있다! 따라서, 방문 배열을 2차원이 아닌 나이트의 이동수까지 포함한 3차원 배열로 구현해.. 2021. 9. 6.

티스토리툴바