DFS
-
[백준] 9944번 NM보드 완주하기문제 풀이 2020. 9. 14. 17:23
9944번 N*M 보드 완주하기 문제) https://www.acmicpc.net/problem/9944 풀이)처음에 구조체 ball을 하나 만들어서, bfs로 구현 시도해보았는데 다시 방문한 곳을 방문처리하기가 까다로웠다. 처음 시도 방법)struct ball { int y, x, dir, cnt, change;ball() {}ball(int y,int x, int dir) {this->y = y; //y좌표this->x = x; //x좌표this->dir = dir; //공이 움직이는 방향this->cnt = 1; //공이 방문한 빈칸 개수this->change = 1; //공이 방향을 바꾼 횟수}}; bool visited[y][x][dir 0 ~ 4] 2번째 시도 방법)방문처리를 back trac..
-
[백준] 4013번 ATM문제 풀이 2020. 9. 5. 19:32
4013 ATM 문제) https://www.acmicpc.net/problem/4013 풀이)SCC, dp를 이용해서 푸는 어려웠던 문제였다. 같은 간선을 여러번 사용할 수 있기 때문에,임의의 정점을 방문한다고 할때 그 정점이 속한 SCC내의 모든 정점을 방문해서 최대 현금을 구한다. 과정1. kosaraju algorithm을 이용해 SCC을 구한다. SCC를 구할때, 각 정점이 어떤 SCC에 속하는지 표시해준다 //int node[i] => i 번 정점이 속하는 SCC번호 각 정점이 속하는 SCC의 총 현금을 저장해준다 //int scc[i] => i 번 SCC의 총 현금, 즉 SCC에 속한 정점들의 현금 합 SCC 끼리 연결될 수 있다면, 그 연결 간선을 저장해준다 //vector adj_scc[..
-
[백준] 2186번 문자판문제 풀이 2020. 8. 15. 19:12
2186 문자판 문제알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자KAKTXEASYRWUZBQP 이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다. X X XX XX X X 반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 ..
-
[백준] 13901번 로봇문제 풀이 2020. 7. 15. 21:10
13901번 로봇 문제해빈이는 로봇을 좋아한다. 로봇을 가지고 놀던 해빈이는 로봇에게 계속해서 명령을 내려 움직이는 대신 이동할 방향을 미리 지정하여 로봇이 알아서 움직이도록 하였다. 이 로봇은 다음과 같은 규칙을 가지고 움직인다.- 로봇은 사용자가 지정한 방향을 일직선으로 움직인다.- 이동 중 벽이나 방문한 지역, 장애물을 만날 경우 로봇은 사용자가 지정한 다음 방향으로 움직인다.- 사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가서 위의 과정을 반복한다.- 로봇이 움직일 수 없을 경우 동작을 멈춘다. 입력으로 방의 크기와 장애물의 개수, 각 장애물들의 위치, 로봇의 시작 위치, 이동 방향의 순서가 주어졌을 때 로봇이 멈추는 위치를 출력하시오. 위치 (0, 0)은 왼쪽 위를 가리키며 방의 크..
-
[백준] 1012번 유기농 배추문제 풀이 2020. 6. 29. 17:47
1012 유기농 배추 문제차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해..
-
[프로그래머스] 보행자 천국문제 풀이 2020. 6. 1. 00:25
문제 설명보행자 천국카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.0인 경우에는 자동차가 자유롭게 지나갈 수 있다.1인 경우에는 자동차 통행이 금지되어 지..
-
[프로그래머스] 방문길이문제 풀이 2020. 5. 30. 00:08
문제 설명게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.U: 위쪽으로 한 칸 가기D: 아래쪽으로 한 칸 가기R: 오른쪽으로 한 칸 가기L: 왼쪽으로 한 칸 가기캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.예를 들어, ULURRDLLU로 명령했다면1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본..
-
[프로그래머스] 등굣길문제 풀이 2020. 5. 19. 17:55
풀이)백준 1520 내리막 문제 풀이를 응용해서 풀었다. (dp와 dfs)다른 점이라면, 최단 경로의 수를 구하는 것이므로 방향을 상하좌우가 아닌 하우만 본다는 것이다.돌아가는 경로를 아예 차단하는 방법 주의점m과 n이 어떤 좌표를 뜻하는지 잘봐야한다.m이 가로고, n이 세로다.물웅덩이도 {m,n} 좌표로 준다. 코드)include #include #include using namespace std; int dp[101][101]; int dy[2] = {1,0}; int dx[2] = {0,1}; #define mod_val 1000000007 int dfs(int y,int x, int m,int n){ if(y== n &&x == m )return 1; if(dp[y][x] == -1){ dp[y]..