일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
- swea
- 세그먼트 트리
- 시뮬레이션
- mst
- 문자열
- 동적계획법
- 이분탐색
- 백준
- 플로이드-와샬
- 위상정렬
- 유니온 파인드
- 알고리즘
- 백트래킹
- 에라토스테네스의 체
- 투 포인터
- 프로그래머스
- Network
- 수학
- dfs
- Effective Java
- 스택
- java
- JUnit 5
- Kotlin
- CS
- 후니의 쉽게 쓴 시스코 네트워킹
- 구현
- 그리디
- BFS
- 완전탐색
목록BFS (24)
반갑습니다!
2234번: 성곽 www.acmicpc.net 풀이 상당히 구현할게 많고 까다로운 문제였다. BFS를 사용해서 방을 분리하고, BFS를 한번 더 사용해서 각 방들끼리의 관계를 인접 리스트로 표현했다. 벽을 한개만 부셔도 2개의 방은 합쳐질 수 있으므로 서로 인접해 있는 방 2개의 합이 가장 큰 경우를 찾아주었다. 코드 #include #include #include #include #include using namespace std; int m, n; bool can_left, can_up, can_right, can_down; int map[51][51]; int area[51][51]; bool chk[51][51]; vector v; vector adj; const int dx[] = { -1, 0..
1600번: 말이 되고픈 원숭이 www.acmicpc.net 못가는 경우가 없는줄 알고 풀었다가 1번 틀렸다.. 문제를 꼼꼼히 읽자.. 풀이 정말 조금 변형된 BFS이다. 4방향 탐색과 말처럼 이동할 수 있는 8방향 탐색을 해주면 된다. 코드 #include #include using namespace std; struct monkey { int x, y, cnt, k_cnt; }; int k, w, h; int map[201][201]; bool visited[201][201][31]; const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 }; const int h_dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 }, h_dy[] = { -2..
1726번: 로봇 www.acmicpc.net 풀이 까다로운 BFS문제이다. 로봇은 한번에 1~3 만큼 이동하거나 방향을 바꿀 수 있다. 이 말은 다른 방향일 때 같은 자리에 위치할 수 있다는 말이므로 중복을 제외하기 위한 visited배열을 생성할 때 3차원 배열로 생성해야해서 해결해야한다. 코드 #include #include using namespace std; struct robot { int x, y, dir, cnt; }; int n, m; int sx, sy, sdir, ex, ey, edir; int map[101][101]; bool visited[101][101][5]; const int dx[] = { 0, 1, -1, 0, 0 }, dy[] = { 0, 0, 0, 1, -1 }; i..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 최소 거리 찾기이므로 BFS로 해결할 수 있지만 로봇이 2칸을 차지한다는 점, 로봇이 회전 가능하다는 점을 유의해야해서 상당히 까다로운 문제이다. 로봇을 구현하기 위해서 규칙을 설정하였다. 1. 로봇이 가로방향인 경우 로봇의 왼쪽부분의 좌표를 저장한다. 2. 로봇이 세로방향인 경우 로봇의 위쪽부분의 좌표를 저장한다. 즉, 아래와 같은 그림의 경우 로봇의 방향은 가로방향으로, 로봇의 좌표는 (0, 0)을 저장한다는 것이다. 로봇을 좌표를 표현할 방식을 결정함으로써 로봇의 회전을 구현하기가 한결 수월해진다...
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 BFS 알고리즘을 사용하여 (1, 1)에서 (n, m)까지 이동횟수를 체크하면 된다. 배열의 인덱스는 0부터 시작하므로 (0, 0)에서 (n-1, m-1)까지 이동횟수로 해결하였다. 코드 #include #include using namespace std; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; int bfs(vector& maps){ int ret = 0; int m = maps.size(); int n = maps[m-1].size(); vec..