티스토리 뷰
728x90
https://www.acmicpc.net/problem/1987
DFS
알파벳으로 구성된 보드판에서 좌측상단부터 시작해서 중복되지 않은 칸을 지나면서 상하좌우로 이동할 수 있다.
이때 최대 몇칸까지 지날 수 있는지 구하는 문제
접근 방법
상하좌우 이동하는 경우들로 DFS로 풀었다.
오답노트
처음에 지나온 알파벳들을 기억하려고 벡터에 지나온 문자들을 담아두고 찾는 식으로 했다가 시간초과나서
알파벳 개수 (26)만큼 boolean 배열에 방문 여부 체크하면서 가는걸로 고쳤다.
아 그리고 visit 배열 처음에 0으로 초기화 안해줬더니 랜덤값 들어가던데 (아니 그냥 Int 배열은 다 0 들어가더만)
근데 왜 DFS함수 시작할 때 방문하는걸로 하면 왜 안될까유
그러면 visit배열을 다시 false로 바꿔주지 않아도 되는거 아닌가..암튼
소스코드
#include <iostream>
using namespace std;
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
int result = 0;
char board[20][20];
int r, c;
void dfs(bool visit[], int cr, int cc, int num){
result = result < num ? num : result;
for(int i = 0 ; i < 4 ; i++){
int nr = cr + dr[i];
int nc = cc + dc[i];
if(nr >= 0 && nr < r && nc >= 0 && nc < c && !visit[board[nr][nc]-'A']){
visit[board[nr][nc]-'A'] = true;
dfs(visit, nr, nc, num+1);
visit[board[nr][nc]-'A'] = false;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> r >> c;
for(int i = 0 ; i < r ; i++){
for(int j = 0 ; j < c ; j++){
cin >> board[i][j];
}
}
bool visit[26] = {0,};
visit[board[0][0]-'A'] = true;
dfs(visit, 0, 0, 1);
cout << result;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 14719] 빗물 (C++) (0) | 2024.08.01 |
---|---|
[백준 2504] 괄호의 값 (C++) (0) | 2024.08.01 |
[백준 9935] 문자열 폭발 (C++) (0) | 2024.07.03 |
[백준 9184] 신나는 함수 실행 (C++) (0) | 2024.07.02 |
[백준 11660] 구간 합 구하기 5 (C++) (0) | 2024.06.24 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- c++
- Stack
- 웹크롤링
- 문자열
- dfs
- 스택
- 이분탐색
- 다이나믹프로그래밍
- Swift
- 파이썬
- 브루트포스
- 정렬
- 자바
- 알고리즘
- 백준
- dp
- 우선순위큐
- 동적계획법
- 프로그래머스
- BFS
- 최대힙
- 투포인터
- 그리디알고리즘
- 게임이론
- 토마토
- 최소힙
- 최단경로
- 수학
- 백트래킹
- 트리
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함