'백준'에 해당되는 글 8건

14500번 주사위 굴리기

https://www.acmicpc.net/problem/14500

문제 해석

테트리스 게임을 조금 활용한 문제같습니다. 문제는 간단합니다.

어떤 판에 숫자들이 적혀있는데 여기서 테트리스모양으로 숫자를 골라 가장 최대가 나오는 값을 구하는 문제입니다.

테트리스 모양은 여러분들이 잘 아시죠? 여기서 물론 테트리스의 블록들은 4방향 회전이 가능합니다.

예제를 직접 풀어보도록 하지요. 아래의 문제의 첫번째 예제가 주어졌습니다.

여기서 가장 큰 수를 고르면 파랑색의 숫자들이 되겠습니다. 이 외에 더 큰 값을 테트리스 모양대로 고를수가 없는 것을 알 수 있습니다.

제약 조건

세로와 가로의 길이(N,M)은 4이상 500이하로 주어집니다. 입력으로 주어지는 수는 1000을 넘지 않는다고 합니다.

풀이

이 문제를 이전에 JAVA로 풀어놓은게 있으므로 이번 포스팅은 JAVA 코드로 구현했습니다.

가로와 세로의 길이는 최대 500이며, 숫자들은 모두 500x500으로 250,000개가 되겠네요. 또 이 중 최대 4개의 숫자만 더하면 되니 문제의 답은 총 4000을 초과하지 않습니다.

이와 같이 문제의 값의 범위가 적을때는 brute-force(전수조사)로 그 문제의 해답을 찾을 수 있습니다. 모든 가능한 수를 구하는 것입니다.

문제를 풀기에 앞서 손으로 테트리스 모양을 만듭시다. 총 7개의 모양을 가지고 있고, 4방향으로 회전을 하기 때문에 대략 28개의 테트리스 모양을 배열로 만들겁니다.

1은 블록이 있는 공간을 말하고 0은 블록이 없는 공간을 의미합니다. 이해가 더 잘가기 위해 아래 세가지 테트리스 블록을 그림으로 첨부했습니다.

이제 이것을 배열로 만드는 것이죠. 이렇게 말이죠. 이 정도 약간의 노가다는 해도 괜찮아요. 시간이 그렇게 많지 않으니까요.

static int [][][]shapes={
		{{1,1,1,1}},{{1},{1},{1},{1}}, 
		{{0,1,0},{1,1,1}},{{1,1,1},{0,1,0}},{{0,1},{1,1},{0,1}},{{1,0},{1,1},{1,0}},
		{{1,1,1},{1,0,0}},{{0,0,1},{1,1,1}},{{1,1},{0,1},{0,1}},{{1,0},{1,0},{1,1}},
		{{1,1,1},{0,0,1}},{{1,0,0},{1,1,1}},{{0,1},{0,1},{1,1}},{{1,1},{1,0},{1,0}},
		{{1,1},{1,1}},
		{{1,0},{1,1},{0,1}},{{0,1,1},{1,1,0}},
		{{0,1},{1,1},{1,0}},{{1,1,0},{0,1,1}}
};

배열 첫번째 모양은 일자모양(l)이고, 두번째는 ㅗ모양입니다. 세번째 모양은 L자 모양이 되겠습니다. 이것을 사방으로 회전하다 보니까 2차원 배열이 한 줄에 최대 4개까지 나오며, 일자모양과 정사각형 모양 등 네 방향으로 회전할때 같은 모양이 나올 경우는 4개까지 나오지 않지요.

실제 문제를 푸는 코드는 아래에 있습니다. 

static int maxValue(int y,int x){
		int max=0;
		for(int next=0;next<19;next++){
			int r=shapes[next].length;
			int c=shapes[next][0].length;
			if(y+r>n||x+c>m) continue;
			int sum=0;
			for(int i=y;i<y+r;i++) for(int j=x;j<x+c;j++)
				sum+=map[i][j]*shapes[next][i-y][j-x];
			max=Math.max(max, sum);
		}
		return max;
	}

인자로 받은 y와 x는 비교할 위치를 말합니다. y는 세로축, x는 가로축의 좌표라고 보면 됩니다.

우리는 회전해서 나온 각각의 모양 19개(3차원 배열속의 2차원 배열 갯수)를 위에서 만들었지 않았나요? 그러니 for문을 19번 반복을 하는 겁니다.

이 for문 안에 r과 c는 만들었던 모양의 가로 길이, 세로 길이를 나타냅니다. 만약 {{ 0,1,0 }, { 1,1,1 }}의 (ㅗ)모양이라면 r의 값은 2, c의 값은 3이 되는 겁니다. 이런 길이가 입력 받은 보드의 범위를 넘어가게 되면 구할 필요가 없어지지요.

그런 조건을 if문으로 거릅니다.

int r=shapes[next].length;
int c=shapes[next][0].length;
if(y+r>n||x+c>m) continue;

범위 안에 있다면 이제 더해주면 됩니다. 우리가 블록이 있는 경우에는 1을 저장했었죠? 블록이 없는 경우는 0을 저장했었습니다. 그래서 판의 숫자에 이 이차원 배열을 단지 곱해주면 됩니다. 이 값을 모두 더하는 것이죠.

sum+=map[i][j]*shapes[next][i-y][j-x];

이제 모든 판의 좌표를 돌면서 가장 큰 값을 구하면 그게 답이 되는 겁니다. 전체 코드는 아래에 있습니다.

import java.util.Scanner;
public class Main {

	static int n,m;
	static int [][]map;
	static int [][][]shapes={
			{{1,1,1,1}},{{1},{1},{1},{1}}, 
			{{0,1,0},{1,1,1}},{{1,1,1},{0,1,0}},{{0,1},{1,1},{0,1}},{{1,0},{1,1},{1,0}},
			{{1,1,1},{1,0,0}},{{0,0,1},{1,1,1}},{{1,1},{0,1},{0,1}},{{1,0},{1,0},{1,1}},
			{{1,1,1},{0,0,1}},{{1,0,0},{1,1,1}},{{0,1},{0,1},{1,1}},{{1,1},{1,0},{1,0}},
			{{1,1},{1,1}},
			{{1,0},{1,1},{0,1}},{{0,1,1},{1,1,0}},
			{{0,1},{1,1},{1,0}},{{1,1,0},{0,1,1}}
	};
	public static void main(String[] ar){
		Scanner in=new Scanner(System.in);
		n=in.nextInt(); m=in.nextInt();
		map=new int[n][m];
		for(int i=0;i<n;i++) for(int j=0;j<m;j++)
			map[i][j]=in.nextInt();
		int max=0;
		for(int i=0;i<n;i++) for(int j=0;j<m;j++)
				max=Math.max(maxValue(i,j), max);
		System.out.println(max);
	}
	static int maxValue(int y,int x){
		int max=0;
		for(int next=0;next<19;next++){
			int r=shapes[next].length;
			int c=shapes[next][0].length;
			if(y+r>n||x+c>m) continue;
			int sum=0;
			for(int i=y;i<y+r;i++) for(int j=x;j<x+c;j++)
					sum+=map[i][j]*shapes[next][i-y][j-x];
			max=Math.max(max, sum);
		}
		return max;
	}
}

이상으로 테트로미노 문제를 풀어보았습니다.

2667 단지번호붙이기

문제 해석

가로 세로 크기가 5에서 25사이의 정사작형 배열에서 1이 뭉쳐져있는 구역을 구하고, 각 구역에서 1이 몇개나 있는지 오름차순으로 출력하라는 문제입니다.

1이 상하좌우에 있다면 그것은 같은 그룹에 속합니다. 아래 사진을 보세요.

<그림 1>에서 1의 그룹은 새 개의 구역으로 <그림 2>로 표현될 수 있습니다. 1번 그룹, 2번 그룹, 3번 그룹이 있고, 각각의 그룹은 7, 8, 9개의 1이 뭉쳐져있는 것이죠. 

입력은 가로, 세로의 길이가 주어지고, 위의 그림처럼 띄어지지 않은 문자열형태로 넘어옵니다. 이렇게 말이죠.

출력은 그룹의 갯수와 각 그룹이 포함하고 있는 1의 개수를 오름차순으로 출력합니다. 

풀이

DFS(Depth First Search)를 이용하면 쉽게 풀 수 있습니다. 우선 입력이 불친절하게 들어오니까 이를 정수형 배열로 바꾸어줍니다. 제가 문자 배열은 왠만하면 사용하기 싫거든요.

scanf("%d", &n);
for (int i = 0; i < n; i++) {
	char line[MAX_N];
	scanf("%s", line);
	for (int j = 0; j < n; j++) 
		map[i][j] = line[j] - '0';
}

배열의 길이 n을 입력받은 후에 for루프를 n번 돌면서 문자 배열 line으로 배열의 한줄을 입력받습니다. 그 for문의 내부 for문에서는 map배열에 실제 입력을 시킵니다. 그래서 map에는 입력들을 정수형 배열로 입력됩니다.

int cnt = 0;
for (int i = 0; i < n; i++) 
	for (int j = 0; j < n; j++) 
		if (map[i][j] == 1) {
			groups[cnt]=dfs(i, j);
			cnt = cnt + 1;
		}

입력을 받았으면 map을 전부 이중for문으로 돌며 1이 있는 부분에서 멈춥니다. 1이 있는 부분에서 멈추게 되면 그 지점에서 dfs를 호출하는 것이죠. dfs가 몇번 호출이 되느냐에 따라서 cnt가 커지게 됩니다. 바로 cnt가 그룹의 전체 갯수를 나타냅니다.

groups에는 cnt라는 그룹에 몇개의 1이 포함이 되어있는지 저장됩니다.

dfs에서 무슨 동작을 할까요? 이 문제를 풀기위한 핵심인 dfs를 보도록합시다.

int dfs(int y, int x) {
	if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 0) return 0;
	map[y][x] = 0;
	return 1 + dfs(y + 1, x) + dfs(y - 1, x)
		+dfs(y, x + 1) + dfs(y, x - 1);
}

dfs함수는 바로 위와 같이 정의되어 있습니다. y는 행, x는 열만을 인자로 받아들이고 있습니다. y나 x가 배열 범위 밖에 있다면 더이상 dfs를 호출하지 않습니다. 또는 map[y][x]가 0인 부분도 기저사례에 포함이 됩니다. 지금까지 말했던 것들이 첫번째 if문의 조건이 되겠네요.

배열 범위에 포함이 되어있으며 map[y][x]=1이라면 바로 그 지점을 0으로 바꿔줍니다. 왜 바꿔주냐면 더 이상 이 점을 방문할 필요가 없으니까요. 만약 map[y][x]=0이 없다면 이 프로그램은 영원히 끝나지 않을겁니다.

그 후에는 상(y-1)하(y+1)좌(x-1)우(x+1)에 dfs를 호출합니다. return에 1을 더해야만 최종 dfs에는 그룹의 1의 개수가 return됩니다.

printf("%d\n", cnt);
sort(groups, groups + cnt);
for (int i = 0; i < cnt; i++) 
	printf("%d\n",groups[i]);

이제 답은 전부 구했네요. cnt를 출력하고 오름차순으로 1의 개수를 출력하라 하였으니 정렬 후에 groups를 출력하면 됩니다.

아래는 전체코드입니다.

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

#define MAX_N 26

int n;
int map[MAX_N][MAX_N];
int groups[MAX_N*MAX_N];
int dfs(int y, int x) {
	if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 0) return 0;
	map[y][x] = 0;
	return 1 + dfs(y + 1, x) + dfs(y - 1, x)
		+dfs(y, x + 1) + dfs(y, x - 1);
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		char line[MAX_N];
		scanf("%s", line);
		for (int j = 0; j < n; j++) 
			map[i][j] = line[j] - '0';
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (map[i][j] == 1) {
				groups[cnt]=dfs(i, j);
				cnt = cnt + 1;
			}
		
	
	printf("%d\n", cnt);
	sort(groups, groups + cnt);
	for (int i = 0; i < cnt; i++) 
		printf("%d\n",groups[i]);
	
	return 0;
}

dfs만 알면 그리 어렵지 않게 풀수 있는 문제였습니다.

LCS(Longest Common Subsequence)

백준 9251번입니다. 문제는 이렇습니다.

임의의 두 수열에서 공통적으로 갖고 있는 가장 긴 부분 수열의 길이를 구하는 것이 문제입니다.

예를 들어 다음과 같은 두 수열이 있다고 합시다.

첫번째 수열과 두번째 수열의 공통수열은 다음과 같습니다.

이 외에도 여러가지 공통 수열이 있지만 가장 긴 수열은 4의 길이를 갖고 있는 ACAK입니다. 두 수열에서 LCS는 여러가지가 있지만 그 길이는 같지요.

제약조건

두 수열을 항상 대문자 알파벳으로 주어지고 각 수열의 길이는 1이상 10000이하입니다.

풀이

이 문제는 생각보다 단순합니다. 두 수열의 문자를 비교해 일치하면 동시에 한칸을 옮겨서 그 다음부터 비교하면 되고, 만약 일치하지 않는다면 두 수열중 아무것이나 한칸 옮겨서 그 다음부터 비교하면 됩니다.

위 두 수열의 LCS길이는 AKEPPA 또는 OKEPPA입니다. 그렇기때문에 답은 6이 나오지요. 이 답이 나오는 과정을 살펴보도록 하겠습니다.

빨간색 글자는 현재 비교할 두 문자입니다. 우선 초기상태이므로 A와 O가 비교됩니다. 두 문자가 일치하지 않으므로 A의 다음 문자를 비교하거나 O의 다음 문자를 비교합니다. 저는 일부러 답을 찾기 위해서 최적의 방법을 사용할 것이니 여러분들은 두 수열 중 어떤 수열을 먼저 한칸 더 옮기든지 상관없다는 것만 아시면 됩니다.

첫번째 수열의 비교 문자를 한칸 옮기니까 두 수열의 문자가 일치하는 군요. 그렇다면 두 수열의 비교문자를 다음으로 옮겨줍니다.

L과 C는 일치하지 않으므로 두 수열중 비교할 문자를 한칸 뒤로 옮깁니다.

이런식으로 이제 계속 비교하다가 보면 언젠가는 다음과 같은 상황이 발생합니다.

이제 K와 K를 비교할 때가 된거죠. K는 두 수열이 두 수열의 비교문자를 모두 다음 위치로 이동합니다.

E 역시 두 문자가 같으므로 다시 또 한칸 동시에 비교문자를 옮깁니다. 옮기고 난 후 보니까 P와 M은 일치하지를 않지요. 그러니까 둘 중 아무 수열이나 비교할 문자를 한칸 옮겨줍니다. 저는 답을 찾기위해 일부터 아래 수열의 비교문자를 한칸 더 옮기겠습니다.

이제 P는 두 수열 모두 같으니 다음 칸으로 옮겨줍니다. 계속 이런식으로 답을 찾으면 결국 다음과 같은 LCS가 나오게 되는 것이죠.

이 LCS는 OKEPPA이고 길이가 6인 것을 알 수 있습니다. 따라서 답은 6이 되는 겁니다.

DP적용

이렇게 답은 찾았는데요. 길이가 10000인 두 수열을 이런식으로 계속 비교하다가는 시간안에 답을 찾기가 힘듭니다. 우리가 자세히 살펴본다면 DP를 적용할 수 있다는 사실을 알 수 있는데요. 만일 수열에서 순서가 A와 O를 비교했는데 아래 배열의 비교 문자를 옮긴다면 A와 C를 비교하게되어 O를 빠뜨리고 가지요. 분명 O는 일치하는 문자임에도요. 

[1][2][3][4][5][6][7][8][9][10]

A O L D M K E P P A

[1][2][3][4][5][6][7][8][9][10]

O C A C K E M P P A

그래서 결국 KEPPA까지만 일치하게 된 상황에서 각 인덱스는 [6][5]입니다. 

따라서 [6][5]에서 가장 긴 수열은 5라고 기억하지요. 그리고 다시 이전으로 돌아가서 비교해야합니다. 그때는 순서를 바꿔 O가 일치하는 상황이 되죠.

[1][2][3][4][5][6][7][8][9][10]

A O L D M K E P P A

[1][2][3][4][5][6][7][8][9][10]

O C A C K E M P P A

이렇게 [6][5]까지 비교한다면 이미 기억해두었으니 제차 끝까지 비교하지 않고 [6][5]까지의 값 5를 반환하기면 하면 됩니다. 그리고 O는 일치했으므로 1을 더하는것이죠. 그래서 답이 6이 됩니다. 이렇게 DP를 적용해서 시간을 줄일 수 있습니다.

구현

다음의 코드는 LCS의 길이를 구하는 코드입니다. 위의 설명을 잘 이해했다면 코드 역시 이해하기가 훨씬 쉬울거에요.

#include <stdio.h>
#include <string.h>

#define MAX(a,b) a>b ? a:b
#define _CRT_SECURE_NO_WARNINGS
char a[1001], b[1001];
int n, m;
int dp[1001][1001];
int solve(int pos1, int pos2) {
	if (pos1 == n || pos2 == m) return 0;
	if (a[pos1] == b[pos2])
		return 1 + solve(pos1 + 1, pos2 + 1);

	int ret = 0;
	if (dp[pos1][pos2] != -1) return dp[pos1][pos2];
	ret = MAX(solve(pos1 + 1, pos2), solve(pos1, pos2 + 1));
	return dp[pos1][pos2] = ret;
}
int main() {

	scanf("%s %s", a, b);
	n = strlen(a); m = strlen(b);
	memset(dp, -1, sizeof(int) * 1001 * 1001);
	int ret = solve(0, 0);
	printf("%d\n", ret);
}

pos1은 첫번째 수열의 비교할 문자 위치, pos2는 두번째 수열의 비교할 문자위치를 말합니다. 만약 pos1과 pos2이 하나라도 수열 끝까지 갔다면 종료되는 것이죠. 이것이 기저 사례입니다.

앞서 말한것과 같이 첫번째 수열의 pos1위치의 문자와 두번째 수열의 pos2위치 문자와 비교해서 같다면 LCS의 길이 1을 더해주고 비교할 문자의 위치 pos1,pos2를 한 칸 증가시켜줍니다.

만약 일치하지 않는다면 둘 중 하나의 수열 비교문자(pos1 또는 pos2)만 한칸 증가시키고 둘 중 가장 큰 값을 반환하면 되죠.

나중에 return할때 메모이제이션으로 값을 업데이트 시키는 것은 잊지 말고 말이죠.

1912번 연속합

문제 해석

수열에서 연속된 수들의 합이 가장 큰 것을 구하는 문제입니다.

10, -4, 3, 1, 5, 6, -35, 12, 21, -1 라는 수열에서 가장 큰 연속은 얼마일까요?

12, 21 부분이 가장 큰 연속합입니다.

연속합의 수들은 한개 이상이라는 점입니다.

음

쉬워보입니다.

처음 시작점을 고정하고 끝점을 하나씩 늘려가면서 시작점과 끝점을 전부 더하는 거죠. 전부 현재의 최대값과 비교해서 크면 그게 최대값이 되는 식으로요.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int nums[100001];

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &nums[i]);

	int ans = -1001;
	for (int start = 0; start < n; start++) {
		for (int end = start; end < n; end++) {
			int sum = 0;
			for (int i = start; i <= end; i++)
				sum += nums[i];
			ans = max(sum, ans);
		}
	}
	printf("%d\n", ans);
}
	

네, 이렇게 제출하면 시간초과랍니다. 하하

입력이 자그마치 10만개가 되거든요.

단순히 이렇게 for루프만 돈다면 문제를 해결할 수가 없습니다.

여기서 간단한 이론(?)이 있는데요.

부분합이라는 개념이 여기 사용됩니다.

우리는 전에 계산한 합을 이용할 수 있다는 거죠.

[0]~[5]까지의 합은 [0]~[4]까지의 합 + 현재의 수를 더하면 된다는 것을 알 수 있습니다.

코드로 본다면 이런 형태이죠.

for (int i = 1; i <= n; i++)
		partialSum[i] = partialSum[i - 1] + numbers[i];

i가 1부터 시작한 이유는 조금 더 보기 편하게 하기 위함입니다. 그러니까 n까지 for루프를 돌아야 됩니다.

그렇다면 [7]~[8]까지의 합만을 구하려면 어떻게 할까요?

partialSum[8]-partialSum[6]을 하게 되면 [7]과 [8]의 부분합만을 구할 수 있습니다.

그럼 1부터 3까지의 합은 partialSum[3]-partialSum[0]이 되겠죠? 인덱스를 왜 1부터 시작하는 지 이유를 알 것 같습니다. 그렇지 않으면 if문을 사용해야합니다.

이제 우리는 위의 코드를 2개의 for문으로 줄일 수 있습니다.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int partialSum[100001];

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int number;
		scanf("%d", &number);
		partialSum[i] = partialSum[i - 1] + number;
	}
	int ans = -1001;
	for (int start = 0; start <= n-1; start++) {
		for (int end = start + 1; end <= n; end++) {
			ans = max(ans, partialSum[end] - partialSum[start]);
		}
	}
	printf("%d\n", ans);
}
	

부분합을 이용해서 이중 for문으로 문제에 접근할 수도 있지만, 이 역시 시간초과가 됩니다. 아까 말한것 처럼 입력이 10만개이기 때문에 이중 for문 역시 시간초과죠.

여기서 한 번 더 줄일 수 없을까요?

부분합을 이용해서 말이죠. 

그전까지 계산한 부분합 + 지금 숫자가 지금 숫자보다 작다면 부분합은 다시 계산 되어야 한다는 것을 직관적으로 느낄 수 있을까요??

그러니까...

현재의 수를 numbers[i]라고 하고 그 전까지 계산했던 부분합이 partialSum[i-1]라고 할때 , partialSum[i]=max(partialSum[i-1]+numbers[i], numbers[i]) 라고 하는 것 말이에요.

다시말해,

partialSum[i]=max(partialSum[i-1]+numers[i], numbers[i])

                =max(지금까지의 부분합, 현재 수)

라고 하는 것이 이해가 가시나요?

지금까지 구한 부분합이 현재의 수보다 작다면 현재의 수부터 다시 부분합을 계산하는 것이 더 클 거니까요.

이것만 이해가 간다면, 다음의 코드는 이 과정을 배열없이 구현했다라는 것을 알 것입니다.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n, partialSum = 0, maxPartialSum = -1001;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		int number;
		scanf("%d", &number );
		partialSum = max(number, number + partialSum);
		maxPartialSum = max(partialSum, maxPartialSum);
	}

	printf("%d\n", maxPartialSum);
	
}
	

코드가 무척이나 짧아졌습니다.

문제의 답은 maxPartialSum입니다. 

코드에서 이 부분을 보세요.

partialSum = max(number, number + partialSum);

number는 현재의 수를 말하는 것이고, partialSum은 이전까지 계산했던 부분합을 의미합니다.

현재의 수와 이전까지 계산했던 부분합 + 현재의 수가 현재의 수보다 작다면 부분합은 다시 현재의 수부터 시작입니다.

이후 이 부분합(partialSum)과 지금까지 부분합의 최대값(maxPartialSum)을 비교해서 큰 값이 다시

maxPartialSum이 되는 것입니다.

2178번 미로탐색

문제 해석

추석인데 할게 없으니, 알고리즘 하나 풀어보자구요!

NxM행렬이 있습니다. N은 행의 수, M은 열의 수인데, 1은 통과 가능한 구역, 0은 통과하지 못하는 공간이라고 문제 설명에서 말합니다.

(1,1)부터 시작해 (N,M)까지 오는데, 가장 적게 1을 통과하는 수를 구하는 게 문제의 답입니다.

아래처럼 빨간 색으로 된 1을 통과하는 게 답이 되겠고, 15가 답이 됩니다.

물론 답은 여러가지가 있을 수도 있겠죠?

위에 빨간점대로 이동하지 않고도 녹색점을 거쳐서 오는 경우도 가능한데, 어차피 답은 똑같다라는 점입니다.

한칸 띄어서 정수형으로 주지 귀찮게

#include <cstdio>
#include <queue>
#include <string>
#include <string.h>

using namespace std;

int n, m;
bool visited[101][101];
char map[101][101];

struct Point {
	int x, y;
	Point(int _y, int _x) {
		x = _x; y = _y;
	}
};

queue<Point> q;

void pushQ(int y, int x) {

	if (y >= n || x >= m || y<0 || x<0 || visited[y][x] || map[y][x] == '0') return;
	q.push(Point(y, x));

	visited[y][x] = true;
}

int bfs() {

	pushQ(0, 0);
	int count = 1;
	while (!q.empty()) {

		int size = q.size();

		for (int i = 0; i<size; i++) {
			Point here = q.front();
			q.pop();

			if (here.y == n - 1 && here.x == m - 1) return count;

			pushQ(here.y + 1, here.x);
			pushQ(here.y - 1, here.x);
			pushQ(here.y, here.x + 1);
			pushQ(here.y, here.x - 1);
		}
		count++;
	}
	return count;
}

int main() {
	scanf("%d %d", &n, &m);

	memset(visited, false, sizeof(visited));
	for (int i = 0; i < n; i++)
		scanf("%s", map[i]);

	printf("%d\n", bfs());
	return 0;
}

위 코드는 단순하게 (0,0) (문제에서는 1,1라고 했지만, 배열은 0,0부터 첫번째 요소이기 때문에)부터 시작해서 (n-1, m-1)( 역시 배열의 가장 마지막 요소는 n-1, m-1)까지 문자열로 입력을 받고,  bfs를 돕니다.

bfs에서는 우선 시작 정점(0,0)을 큐에 집어 넣습니다. 그 후에 bfs의 size를 호출해 포문을 돌고 그 상하좌우의 정점을 집어 넣게 되는 겁니다. 주의해야할 점은 for루프 조건문에서 직접적으로 q.size()를 호출하면 안된다는 점입니다. for루프 안에서 q에 push되므로 for문을 한번 돌때마다 q.size()가 유동적으로 바뀌게 됩니다.

                int size = q.size();

		for (int i = 0; i<size; i++) {
			Point here = q.front();
			q.pop();

			if (here.y == n - 1 && here.x == m - 1) return count;

			pushQ(here.y + 1, here.x);
			pushQ(here.y - 1, here.x);
			pushQ(here.y, here.x + 1);
			pushQ(here.y, here.x - 1);
		}
		count++;

그렇게 for문을 한 번 돌면 그 주위에 있는 정점 한번을 탐색한 것이니까 count를 하나 증가시켜 주고요. 만약 n-1, m-1 정점까지 도달했다면 바로 이 count를 return하게 되면 몇 번만에 (n-1, m-1)까지 도달했는지 알 수 있습니다.

pushQ함수는 조건에 맞지 않는 정점은 그냥 지나쳐 버립니다.

조건에 맞지 않는 정점이라는 것은 범위밖의 정점( 0보다 작거나 n또는 m보다 큰 정점), 이미 방문된 정점, 또는 0인 정점을 말하는 것이죠.

방문해야 할 정점이라면 큐에 push하고 방문되었다는 표시만 해주는 아주 단순한 함수입니다. visited[y][x] = true가 바로 방문되었다는 표시를 해주는 작업이랍니다.

단순하긴 하지만 이 함수가 없다면 for루프 안에 일일히 if문으로 검사를 해주어야하는 뻘짓을 하게 될겁니다.

void pushQ(int y, int x) {

	if (y >= n || x >= m || y<0 || x<0 || visited[y][x] || map[y][x] == '0') return;
	q.push(Point(y, x));

	visited[y][x] = true;
}

그리고 또 한가지는 pushQ를 총 4번 호출하죠?

for문으로 돌릴 수 있으나, 거기까지 생각하면서 귀찮게 코딩 안하잖아요 우리는...

그냥 짧은거는 복붙합시다... 티도 안나요.

점(point)을 조금 편하게 관리하게 위해서 Point라는 구조체를 사용했습니다.

뭐... 사용하지 않고 그냥 배열로만 해도 상관없구요.

십쥬?

1463번 1로 만들기

문제 해석

문제는 너무 간단 합니다. 세가지 규칙이 있는데요.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이렇게 만들어서 1로 만들어라 이겁니다. 12를 최소로 위 규칙을 사용하면 어떤 과정을 거칠 수 있을까요?

12 - 4(1번 규칙 적용) - 2(2번 규칙 적용) - 1(2번 또는 3번 규칙 적용)

이렇게 3번으로 1을 만들 수 있다는 건데요. 

36은 어떻게 구할 수 있을까요?

36 - 12(1번 규칙 적용)

12는 위에서 구했습니다. 감이 오시죠? DP냄새가 나지 않습니까?

#include <cstdio>
#include <string.h>

#define min(x,y) x<=y ? x:y
#define INF 987654321
using namespace std;

int dp[1000001];

int solve(int n) {

	if (n == 1) return 0;
	if (dp[n] != -1) return dp[n];

	int ret = INF;
	if (n % 2 == 0) ret = 1 + solve(n / 2);
	if (n % 3 == 0) ret = min(ret, 1 + solve(n / 3));
        //ret = min(ret, 1+solve(n-1));
	if (n % 6 != 0) 
		ret = min(ret, 1 + solve(n - 1));

	return dp[n] = ret;
}

int main() {

	int n;
	scanf("%d", &n);

	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(n));
}

n을 규칙대로 3으로 나누어 떨어지면 3으로 나누고, 2로 나누어 떨어지면 2로 나누고, 또는 1을 뺀 규칙을 적용해서 1로 만들어보는 것입니다. 3으로 나누어 떨어지지 않거나, 2로 나누어 떨어지지 않을 땐 1을 빼는 규칙을 적용해줍니다.

왜요?

n을 1로 만들어주는데 있어서 2와 3으로 나누는 것이 유리하다는 것이죠. 어떤 수로 나누는 것이 n을 줄이는 일에 효과적이라는 겁니다. 그래서 1을 최소로 빼주고 될 수 있으면 2와 3으로 나누는 편이 더 좋습니다.  그러니 2와 3의 최소 공배수 6을 이용해서 6으로 나누어 떨어지지 않으면 1을 빼는 것을 시도하는 것입니다.

위 코드의 주석을 해제하고 if문 부분을 주석처리하여 제출해보세요. 결과는 맞지만 효율성에서 차이가 나는게 보일겁니다.

1012번 유기농 배추

문제 해석

문제는 여러가지 방법으로 풀 수 있습니다.

문제는 간단히 말해 이렇답니다.

그냥 1이 뭉쳐저 있는 곳을 세는 겁니다. 

단, 1은 상하좌우를 통해서 연결되어 집니다. 대각선으로 1은 서로 다른 지역으로 인식하게 되는 겁니다.

위의 예제에서는 1이 뭉쳐져 있는 곳이 총 5부분입니다. 그래서 답이 5가 되는 것입니다.

이런 문제는 조금 흔한 문제라서 딱 보면 그거네~ 하실 거에요.

제약 조건

테스트케이스 T가 주어지고 N과 M은 1이상 50 이하입니다. 배추가 심어져 있는 점은 Y, X로 주어집니다.

최대 50*50이 주어질 수가 있겠군요. 

풀이

이 유기농배추가 있는 지도를 그래프로 생각을 해보도록 하겠습니다. 탐색 방법은 어떤 방향이든 좋습니다. 하지만 상하좌우 네 방향을 전부 탐색해야합니다. 단, 1인 정점만 탐색합니다.

현재 위치를 y,x라고 치고 상하좌우를 탐색합니다. 위쪽 정점은 현재 정점의 y-1, x 아래 정점은 현재 정점의 y+1,x, 왼쪽 정점은 현재 정점의 y, x-1, 오른쪽 정점은 현재 정점의 y, x+1입니다.

하지만 이미 방문되었다면 그 정점은 탐색하지 않습니다.

따라서 dfs가 몇번 호출되었는가가 이 문제의 답이됩니다. 코드를 통해서 살펴보도록 할까요?

#include <cstdio>
#include <string.h>
#define M 51
#define VISITED 0
using namespace std;

int n, m, k;
int map[M][M];

void dfs(int y, int x) {
	
	if ( y<0 || y >= n || x < 0 || x >= m || map[y][x] == VISITED )
		return;

	map[y][x] = VISITED;
	dfs(y + 1, x);	dfs(y, x + 1);
	dfs(y - 1, x);	dfs(y, x - 1);
}

int main() {
	int T;

	scanf("%d",&T);
	for (int t = 0; t < T; t++) {

		memset(map, 0, sizeof(map));

		scanf("%d %d %d", &m, &n, &k);
		for (int i = 0; i < k; i++) {
			int y, x;
			scanf("%d %d", &y, &x);
			map[x][y] = 1;
		}

		int count = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++)
				if (map[y][x] == 1) {
					dfs(y, x);
					count++;
				}
		}
	
		printf("%d\n", count);
	}
}

이중 for문을 돌며 1이 등장하면 그 정점부터 dfs를 실행합니다.  dfs는 그 정점이 0이거나 y, x가 범위 밖이면 바로 return 됩니다.

그렇다면 우리는 그냥 0을 방문되었다고 표현하면 더 간단하게 문제를 풀 수 있지 않을까요?

아래 사진처럼 0,0에서 1을 만났다고 치겠습니다. 그렇다면 그 지점 0,0에서 dfs를 수행하면 앞뒤 양옆을 dfs로 순차적으로 돌아 전부 방문됩니다. 그러면 0으로 값이 변하게 되지요. 이 부분이 두번째 사진의 빨간색으로 된 0으로 표현을 했네요.

dfs가 끝났으니 for문을 계속 수행합니다. 하지만 이미 dfs가 돌아 0으로 값이 변했으므로 skip됩니다.

이런 식으로 dfs를 한번 돌게 되면 하나의 덩어리를 구할 수 있습니다. 이 덩어리의 수를 세는 것이 답입니다.

답은 위 코드의 count로 표현됩니다.

시간 복잡도는 N*M이 됩니다. 

이외에도 BFS를 통해서도 문제의 해답을 구할 수도 있습니다. 

마찬가지로 for문 속에서 일일이 루프를 돌면서 아직 방문되지 않는 점이 있으면 bfs를 돌고 count에 1을 더해 주기만 하면 되거든요.

BFS나 DFS나 둘 중 하나만 알아도 이 문제는 풀 수 있습니다.

또 어떤 방법으로 풀 수 있을까요??

1932번 정수 삼각형

문제가 이해되셨나요?

맨 위 삼각형 꼭지점에 있는 숫자부터 시작해서 아래까지 계속하여 더합니다. 그 중 가장 큰 수를 구하는 것입니다. 

하지만 조건이 걸려있지요! 바로 위에서 아래로 내려올때 대각선 왼쪽, 또는 오른쪽으로 내려오면서 그 숫자를 더하는 겁니다. 

문제에 있는 예제부터 보겠습니다.

#include <stdio.h>
#include <string.h>
#define N 501
#define max(a,b) a>b ? a:b

int triangle[N][N], dp[N][N];
int n;
int solve(int y, int x) {
	if (y>n || x>n ) return -99999999;
	if (y == n) return triangle[y][x];
	if (dp[y][x] != -1) return dp[y][x];
	int ret = 0;
	ret = max(triangle[y][x] + solve(y + 1, x),
		triangle[y][x] + solve(y + 1, x + 1));
	return dp[y][x] = ret;
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			scanf("%d", &triangle[i][j]);
	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(1, 1));
	
}