2주차 (2021년 01월 06일)
목표
-
인프런 파이썬 강의 1시간 수강
-
수강 후 내용 실습
-
알고리즘 < BFS/DFS > 문제풀기 (백준 2178번, 백준 1012번)
회고
-
인프런 파이썬 강의 40분 수강
-
배운 내용 jupyter notebook을 사용해서 실습
-
알고리즘 < BFS > 문제 : 백준 2178번(“미로 찾기”) -> 난이도 : 실버1
해결 방법 : 미로의 시작점부터 큐에 넣은 후에 큐에서 하나씩 빼면서 길이 있고 방문하지 않은 경우, 그 길의 값은 그 전 길의 값에 1을 더해간다. 그리고 미로 출구의 값을 출력한다.
코드일부
while(!q_x.isEmpty()) { // BFS
int x = q_x.poll();
int y = q_y.poll();
for(int i = 0; i < plusX.length; i++) {
int new_x = x + plusX[i]; // 현재지점에서 새로운 x값
int new_y = y + plusY[i]; // 현재지점에서 새로운 y값
if(new_x >= 0 && new_x < row && new_y >= 0 && new_y < col) { // 새로운 x,y의 값이 범위 안이고
if(maze[new_x][new_y] == 1 && visit[new_x][new_y] == false) { // 새로운 [x,y]지점이 길이 있고, 방문하지 않은 경우
q_x.add(new_x);
q_y.add(new_y);
maze[new_x][new_y] = maze[x][y] + 1;
visit[new_x][new_y] = true;
}
}
}
}
- 알고리즘 < DFS > 문제 : 백준 1012번 (“유기농 배추 문제”) -> 난이도 : 실버2
해결 방법 : DFS를 사용하는 문제여서 DFS함수를 구현했다. 배추가 상하좌우에 위치하는 경우 DFS를 계속해서 하고 더이상 붙어있는 배추가 없을 경우 count 값을 1씩 올린다. 다 끝난 후에 count값을 출력한다.
코드일부
public static void Dfs(int x, int y) {
visit[x][y] = true;
for(int a = 0; a < plusX.length; a++) {
int new_x = x + plusX[a]; // 현재지점에서 새로운 x값
int new_y = y + plusY[a]; // 현재지점에서 새로운 y값
if(new_x >= 0 && new_x < row && new_y >= 0 && new_y < col) { // 새로운 x,y의 값이 범위 안이고
if(field[new_x][new_y] == 1 && visit[new_x][new_y] == false) { // 새로운 [x,y]지점이 길이 있고, 방문하지 않은 경우
Dfs(new_x, new_y);
}
}
}
}