알고리즘

[백준]14499번 주사위 굴리기 - Java

문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 시뮬레이션 문제이다. 주사위를 어떻게 굴릴지만 구현하면 된다! 나는 주사위 전개도를 2차원 배열로 보고 동서북남 방향으로 굴릴 경우, 어떻게 전개도가 바뀔지 생각해서 구현했다. 1차원 배열 2개로 전개도를 구현하거나, 클래스를 만들어서 주사위의 윗면, 아랫면, 앞면, 뒷면, 왼쪽면, 오른쪽면을 구현해도 같은 결과를 얻을 ..

[백준]3055번 탈출 - Java

문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 bfs 문제임! 주의할 점은 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 이렇기 때문에 물을 먼저 bfs로 퍼지게 하고 그 후에 고슴도치를 bfs로 이동시켜야 한다! 나는 큐를 두개 만들어서 풀었지만 큐 하나로도 가능할 것 같다!! 자세한건 주석으로! 코드 // 3055번..

[백준]5212번 지구 온난화 - Java

문제 https://www.acmicpc.net/problem/5212 5212번: 지구 온난화 첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다. www.acmicpc.net 풀이 그냥 이차원 배열 돌면서 3면 이상이 바다면 땅을 물에 잠기게 해주면 된다. 새로운 정답 2차원 배열 지도를 만들어서 물에 잠긴 땅이 다음 칸에도 영향을 주지 않게 하였음! 정답 지도를 그릴 때는 다시 정답 배열을 돌면서 범위 체크를 위한 변수를 최신화하고 그 범위 내의 지도만 그려줌! 위의 두 가지만 조심하면 어렵지 않게 금방 풀 수 있는 문제임!!! 자세한 건 주석으로!! 코드 // 5212번 지구 온난화 // https://www.acmicpc.net/pro..

[백준]11559번 Puyo Puyo - Java

문제 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 처음에 어떻게 풀지 설계를 안하고 풀다보니까 중간에 한번 엎었다... 문제 좀 똑바로 읽고 풀자 쫌...!!!!! 쭈욱 돌면서 뿌요가 있으면 같은 색의 뿌요가 4개 이상 인접해있는지 dfs()로 판단하다가 4개가 넘어가면 그 위치에서 다시 dfsBomb()를 돌려서 연결되어 있는 뿌요를 다 없앰! 그리고 다른 색의 뿌요도 4개 이상이 인접해 있는 경우가 있으니까..

[백준]14891번 톱니바퀴 - Java

문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 아 처음에 톱니바퀴의 위치에 따라서 옆 톱니바퀴가 회전하는지 안하는지를 생각을 안해줘서 너무 노가다로 풀었다,,,, 진짜 너무 빡침 ㅠ 이래서 설계가 중요하구나 느꼈음./... 중간에 코드 짜다가 아 이렇게 풀면 안되는구나 하고 알았는데 톱니바퀴 4개라서 노가다도 될 것 같고, 이미 돌아가기엔 너무 늦었으니까 이렇게 풀고 다음에 톱니바퀴2 문제나 이 문제 한번 더 풀어야 겠다 라고 ..

[백준]7569번 토마토 - Java

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 https://seokmimmmmmmmm.tistory.com/98 [백준]7576번 토마토 - Java 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000.. ..

[백준]2606번 바이러스 - Java

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 뭐 여러가지 방법을 풀 수 있겠지만 인접 행렬로 풀면 쓸데없는 메모리 활용이 좀 있을 것 같다. 그래서 ArrayList를 활용한 인접 리스트로 풀었음. 방문 체크 배열을 이용해서 이미 방문한 곳은 체크를 하고 인접한 애들 중 방문하지 않은 애들인 경우에만 answer++하고 dfs를 한번 더 탔음! 밑에 코드 참고! 코드 // 2606번 바이러스 // https://www.acmicpc.n..

[백준]3190번 뱀 - Java

문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 시뮬레이션 문제이다. 뱀을 큐로 생각했고, 다음 칸의 좌표를 뱀 큐에 넣어주고 그 칸이 사과면 큐의 길이를 줄이지 않고(poll()하지 않고) 사과가 아니면 큐의 길이를 줄였음(poll()했음). 그리고 방향 전환은 4방향을 시계방향으로 해줬음(시계 반대 방향이여도 상관 없음). 4방 탐색이므로 +를 해서 4가 넘어가면 %4 연산을 통해서 방향이 돌고 돌 수 있게 해줌 이것들만 생각하면 잘 풀..