본문 바로가기
728x90
반응형

코딩테스트190

[백준/java] 7569번 : 토마토(3차원배열) BFS 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net ※ 문제풀이 이번 문제는 2차원 배열로 푸는 토마토 문제(7576)와 방법은 똑같고 다만 3차원배열이어서 동서남북 + 위 아래까지 조회를 해주면 된다. 그러면 7576번 토마토와 비교해서 어떤 것이 추가되었는지 확인해보자. 먼저 변수 선언부 static int[][][] map; static boolean[][][] visit; static int M, N, H; static int[][] dx, dy, dh; static class No.. 2021. 8. 15.
[백준/java] 7562번 : 나이트의 이동(체스 나이트의 이동) - BFS https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 토마토 문제처럼 이번 문제도 Queue에 넣는 클래스가 y, x값 말고도 cnt가 하나 더 들어갔다. 이것의 용도는 최단거리를 측정할 때 사용하는 것! 이제 점점 BFS로 순회할 때 최단거리를 계산하는 방법이 조금씩 감이 오는 것 같다. 이 문제에서 int형 이차원 배열이 따로 사용되지는 않았다. 방문하는 곳마다 값을 확인할 필요가 없었기 때문이다. 이 문제를 풀때 오래걸리고 오해했던 것은 도착지로.. 2021. 8. 15.
[백준/java] 7576번 : 토마토 - BFS https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ※ 문제 풀이방식 BFS가 응용된 부분 위주로 설명 드리겠습니다 (1) 우선 dy, dx 배열의 값은 두개의 값들을 함께보면 (1, 0), (0, 1), (-1, 0), (0, -1) 이 순으로 되어있습니다. --> 이것이 의미하는 것은 북 동 남 서 방향으로 방향을 설정하는 것입니다. (2) Node 클래스에 기존에 풀이했던 그림, 섬의 개수, 안전 영역같은 문제들과는 달리 x,.. 2021. 8. 14.
[백준/java] 2468번 : 안전 영역 - BFS https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 어렵지도, 그렇다고 그렇게 쉬운문제는 아니었다. 생각보다 놓치기 쉬운 함정들이 있었다. 입력의 마지막 설명 중, " 높이는 1이상 100 이하의 정수이다. " 라는 설명이 있는데, 문제 페이지 맨 마지막 "노트"란을 보면 라고 나와있다. 이것을 고려하지 않는 경우가 더러 있었다고 한다. bfs로 순환하여 탐색하되, 순환의 높이의 시작은 0부터 100까지여야 한다는 것이다. package bfs; impo.. 2021. 8. 14.
[백준/java] 4963번 : 섬의 개수 - BFS https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 드디어.. 처음으로 BFS 개념을 어느 곳에서도 참고하지 않고 혼자 힘으로 푼 문제이다 문제 자체는 어려운 문제는 아니었다. ※ 문제 풀이 접근 방법 (1) 이차원 배열 map으로 배열의 크기 다음으로 입력되는 값들을 입력받는다 (2) map 이차원 배열의 크기와 똑같은 사이즈의 boolean형 이차원 배열을 만들어준다. (3) 이중으로 for문을 돌면서, map[i][j]가 1이 아니거나 .. 2021. 8. 13.
[백준/java] 14891번: 톱니바퀴 - 삼성 코딩테스트 기출문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 프로세스 순서 착오에 의해 문제를 푸는데만 3일이 넘게 걸렸다.. 대충 이해했던 프로세스는 아래와 같다. ---> 1. 지정받은 번호의 톱니바퀴를 방향에 맞게 일단 회전시킨다. ---> 2. 회전시킨 후, 왼쪽과 오른쪽 톱니바퀴의 극을 비교한다 ---> 3. 극이 다르면 비교 대상의 톱니바퀴를 반대방향으로 회전시킨다. ---> 4. 2 ~ 3번을 반복한다 로 이해했었는데 아주 잘못된 이해였다.. 2021. 8. 13.
728x90
반응형

티스토리툴바