Shining...

첫 줄은 배달해야 하는 장소의 수 N(1≤N≤12)이 주어진다. 이때, 출발지(회사)는 1번이다. 

둘째 줄은 N X N 크기의 장소와 장소를 이동하는 비용(0 ≤ 비용＜ 100)이 한 칸씩의 공백으로 구분하여 주어진다. 비용은 양방향이 아니라 단방향으로 가기 위한 비용이다. 예들 들어 첫 번째 행 두 번째 열에 적힌 비용은 1번 장소에서 2번 장소로 이동하기 위한 비용을 의미하며, 2번 장소에서 1번 장소로 이동하기 위한 비용은 두 번째 행 첫 번째 열에 주어진다.
장소 사이에 이동할 수 있는 방법이 없다면 비용을 0으로 표시한다.

회사에서 출발하여 오늘 배달해야 하는 모든 장소를 한 번씩 들러 물건을 배달하고 회사에 돌아오기 위한 최소의 비용을 출력한다.

[Copy] 5 0 14 4 10 20 14 0 7 8 7 4 5 0 7 16 11 7 9 0 2 18 7 17 4 0

[Copy] 30

테스트 코드를 이 배열로하면 문제가 별 안보이지만, 아래아래 6짜리로 하면 예외 케이스를 확인할 수 있다. 이것만 유의하면 문제 없음

예산관리와 유의하여 볼 것.

5 

0 14 4 10 20 

14 0 7 8 7 

4 5 0 7 16 

11 7 9 0 2 

18 7 17 4 0

이 배열로하면, 

6

0 93 23 32 39 46 

0 0 7 58 59 13 

40 98 0 14 33 98 

3 39 0 0 13 16 

51 25 19 88 0 47 

65 81 63 0 6 0 

#include<stdio.h>

int N;

int map[110][110];

int sol = 0x7fffffff;

int max = 0x7fffffff;

int chk[13];

void dfs(int V, int r, int cost) // V는 접점의 개수를 counting, r은 각 들어갈 열, cost는 총 비용

{

if (cost >= sol) return; //만약 현재값이 sol보다 커버리면 아무의미 없으니까 skip

if (V >= N)

{

if (map[r][1] == 0) { 

return; /* 1로 돌아갈때, 돌아올 수 못한 다는 것을 의미 */

}

cost += map[r][1];//비용 증가

if (cost < sol) sol = cost;

return;

}

for (int i = 2; i <= N; i++)

{

if (r == i) continue;//똑같은 곳에서 똑같은 곳으로 갈일은 없으니 skip

if (!chk[i] && map[r][i])//들러보지 않은 곳

{

chk[i] = 1;

dfs(V + 1, i, cost + map[r][i]);

chk[i] = 0;

}

}

}

void main()

{

freopen("input.txt", "r", stdin);

scanf("%d", &N);

for (int i = 1; i <= N; i++)

for (int j = 1; j <= N; j++)

scanf("%d", &map[i][j]);

dfs(1, 1, 0);

printf("%d", sol != max ? sol : 0);

}

f(i, sum) = i번째 활동을 고려할 때, i-1까지 활동비용의 합계가 sum인 경우
#include <stdio.h>
int B/*예산*/, n/*개수*/, act[23], res;

void f(int i, int sum)  // i번활동, i-1까지의 합계

{   

if(i==n+1)   

{     

if(sum<=B && sum>res) //예산 보다는 작고 현재 값보다는 크면.

res=sum ;

return;

}

f(i+1, sum+act[i]); // i번째 활동을 포함하거나

f(i+1, sum);         // 포함하지 않 거나

}
int main() {

int i;

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

for(i=1; i<=n; i++)

scanf("%d", &act[i]);

f(1, 0);

printf("%d", res);

return 0;

}

배낭 문제(S)

f(i, r) = i~n번째 물건까지 고려했을 때, 남은 무게가 r인 가치의 최대 합
#include <stdio.h>
int W, n, i, j, w[102], v[102]; 
int max(int a, int b) {return a>b ? a:b;}
int f(int i/*물건번호*/, int r/*남은무게*/)
{ 
    if (i == n + 1)      
        return 0;  
    else if (r<w[i])     //만약 남은무게가 현재 물건크기보다 작다면.. 다음물건으로 진행
        return f(i + 1, r);  
    else     
        return max(f(i + 1, r), f(i + 1, r-w[i]) + v[i]);
}  

int main()
{
 scanf("%d %d", &n, &W);  
 for (i = 1; i <= n; i++)   
  scanf("%d%d", &w[i], &v[i]);  
 printf("%d", f(1, W));  
 return 0;
}

더하기

int T, N/*개수*/, K/*합계*/;

int d[20];

int sol;

int DFS(int x, int sum)

{

if (sum == K) return 1;

if (x >= N) return 0;

if (sum + d[x] <= K)

{

if (DFS(x + 1, sum + d[x]) == 1) return 1;

}

if (DFS(x + 1, sum) == 1) 

{ return 1; }

return 0;

}

int main(void)

{

freopen("input.txt", "r", stdin);

int i;

scanf("%d", &T);

while (T--)

{

scanf("%d %d", &N, &K);

for (i = 0; i<N; i++)

{

scanf("%d", &d[i]);

}

if (DFS(0, 0)) printf("YES\n");

else printf("NO\n");

}

return 0;

}

//등산로

#include <stdio.h>

int N;//산의크기(지도의크기)

int DY;//정상의세로위치

int DX;//정상의가로위치

int map[110][110];//산의정보

int D[110][110];//힘을계산해서갱신할배열

struct st {

int r, c;//r:세로위치, c:가로위치

};

#define MAXQ (110*110*10)

#define INF (0x7FFFFFFF)

struct st queue[MAXQ];

int wp, rp;

int In_Queue(int r, int c) {

if (wp >= MAXQ) return 0;//저장실패

queue[wp].r = r;

queue[wp++].c = c;

return 1;//성공

}

int Out_Queue(struct st *p) {

if (wp == rp) return 0;//읽기실패

*p = queue[rp++];

return 1;//성공

}

int BFS(void) {

int rr[] = { -1, 1, 0, 0 };

int cc[] = { 0, 0, -1, 1 };

int i, j, temp, r, c;

struct st p;

//D배열INF값으로초기화, 시작위치를큐에저장

for (i = 0; i<N + 2; i++) {//세로

for (j = 0; j<N + 2; j++) {//가로

if ((i == 0) || (j == 0) || (i == N + 1) || (j == N + 1)) {

In_Queue(i, j);

D[i][j] = 0;

}

else D[i][j] = INF;

}

}

while (Out_Queue(&p)) {

for (i = 0; i<4; i++) {

r = p.r + rr[i];//p.r은현재위치, r은이동할위치

c = p.c + cc[i];//p.c는현재위치, c는이동할위치

if ((r>0) && (c>0) && (r<N + 1) && (c<N + 1)) {//이동가능

temp = map[p.r][p.c] - map[r][c];//현재위치높이- 이동할위치의높이

if (temp < 0) temp *= temp; //오르막길(차의제곱만큼힘이듦)

temp += D[p.r][p.c];

if (D[r][c] > temp) {//기존보다힘이적게들때만갱신

D[r][c] = temp;

In_Queue(r, c);

}

}

}

}

return D[DY][DX];

}

int main(void) {

int i, j, sol;

scanf("%d", &N);

scanf("%d %d", &DY, &DX);

for (i = 1; i <= N; i++) {

for (j = 1; j <= N; j++) {

scanf("%d", &map[i][j]);

}

}

sol = BFS();

printf("%d\n", sol);

return 0;

}

//영역구하기

typedef struct {

int sX;

int sY;

int eX;

int eY;

} _pos;

_pos POS[1000];

int map[100][100] = { 0, };

int nCount = 0;

int nArea = 0;

int Area[100] = { 0, };

int sero;

int garo;

int idx = -1;

void find(int se, int ga)

{

nCount++;

if (se - 1 >= 0 && map[se - 1][ga] == 0) 

{

map[se - 1][ga] = idx;

find(se - 1, ga); 

}

if (se + 1 < sero && map[se + 1][ga] == 0)

{ 

map[se + 1][ga] = idx; 

find(se + 1, ga); 

}

if (ga - 1 >= 0 && map[se][ga - 1] == 0) 

{ 

map[se][ga - 1] = idx; 

find(se, ga - 1); 

}

if (ga + 1 < garo && map[se][ga + 1] == 0)

{ 

map[se][ga + 1] = idx;

find(se, ga + 1); 

}

//int Dy[] = { 1, 0,0, -1 };

//int Dx[] = { 0,-1, 1, 0 };

//nArea++;

//int head = 0;

//int tail = 1;

//while (1)

//{

// for (int x = 0; x < 4; x++)

// {

// int tmpX = garo + Dx[x];

// int tmpY = sero + Dy[x];

// if (map[tmpY][tmpX] == 0)

// {

// map[tmpY][tmpX] == -1;

// nCount++;

// }

// }

//}

}

void main()

{

int count;

// freopen("input.txt", "r", stdin);

scanf("%d %d %d", &sero, &garo, &count);

for (int i = 0; i < count; i++)

{

scanf("%d %d %d %d", &POS[i].sX, &POS[i].sY, &POS[i].eX, &POS[i].eY);

int tmpX = POS[i].eX - POS[i].sX;

int tmpY = POS[i].eY - POS[i].sY;

for (int y = POS[i].sY; y < tmpY + POS[i].sY; y++)

{

for (int x = POS[i].sX; x < tmpX + POS[i].sX; x++)

{

map[y][x]++;

}

}

}

for (int i = 0; i< sero; i++)

{

for (int j = 0; j < garo; j++)

{

if (map[i][j] == 0)

{

map[i][j] = --idx;

find(i, j);

Area[nArea++] = nCount;

nCount = 0;

}

}

}

for (int i = 0; i < nArea-1; i++)

{

for (int j = 0; j < nArea - 1 -i; j++)

{

if (Area[j] > Area[j + 1])

{

int tmp = Area[j];

Area[j] = Area[j + 1];

Area[j + 1] = tmp;

}

}

}

printf("%d\n", nArea);

for (int i = 0; i < nArea; i++)

{

printf("%d ", Area[i]);

}

}

/*문제 설명

n×n의 행렬로 지형도가 표시된 산이 있다.행렬의 원소의 값은 양의 정수 값으로 그 위치에서의 높이를 말해준다.등산가들은 산의 바깥지역(높이 0)으로부터 정상에 도달하기 위하여 가장 경제적인 루트를 탐색하려고 한다.경제적인 경로란 힘을 가장 적게 들이고 정상까지 올라갈 수 있는 길을 말한다.

예를 보면서 설명해보자.다음은 행렬 Mount[5, 5]로 표시된 산악지형이다.산의 정상은 Mount[3, 3]의 위치에 있으며, 그 높이는 6이다.그리고 이 산의 바깥지역은 모두 해발이 0이다.등산가가 산에 오르는 시작점의 위치는 산의 바깥지역의 어디에서 시작해도 좋다.

등산가는 어떤 한 지역에서 그 위치에 인접한 네 방향(위, 아래, 왼쪽, 오른쪽)으로만 움직일 수 있다.인접한 지역으로 움직일 수 있는 경우는(1) 평지로 이동할 경우, (2) 내려갈 경우, (3) 올라갈 경우의 세 가지이다.이 세 가지 경우에 필요한 "힘"의 양은 다음과 같이 표현될 수 있다.

(1)인접한 같은 높이의 지역을 수평 이동할 경우에는 그냥 평지를 걸어가면 되므로 힘이 전혀 들지 않는다고 가정한다.예를 들면 Mount[5, 2]에서 Mount[5, 3]으로 이동하는 경우와 Mount[4, 5]에서 Mount[5, 5]로 이동하는 경우에는 전혀 힘이 들지 않는다.

(2)내리막길을 따라갈 경우(예를 들면, Mount[2, 3]에서 Mount[2, 2]로 갈 때)에는 그 높이 차이만큼의 힘이 든다.즉 이 경우에는 5 - 3 = 2만큼의 힘이 든다.

(3)오르막길을 오를 경우에는 이동할 두 지역의 높이 차의 제곱만큼의 힘이 든다.즉 Mount[1, 2]에서 Mount[1, 3]으로 갈 경우는(4 - 2)2 = 4 만큼의 힘이 든다.

입력

첫째 줄에는 산의 크기인 Mount[n, n]의 n값이 주어지고, 두 번째 줄에는 정상의 위치 Mount[y, x]의 y, x값이 주어진다.

단, Mount[n, n]에서 n은 100이하이고, 각 지형의 최대 높이는 50이하라고 가정한다.

그 다음 n개의 줄은 산의 크기에 따른 각 지점의 높이가 양의 정수 값으로 주어진다.

출력

첫째 줄에 정상까지 도달하는 가장 경제적인 경로를 따라 올라가는데 사용된 힘을 출력한다.

입력 예시

5

3 3

1 2 4 3 2

1 3 5 4 4

2 3 6 5 1

3 1 4 1 3

2 3 3 5 3

출력 예시

8

도움말

경로는 다음과 같다.

2[1, 5]->3[1, 4]->4[2, 4]->5[3, 4]->6[3, 3]

= 2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 + 1 * 1

= 8

*/

#include<stdio.h>

/*

5

3 3

1 2 4 3 2

1 3 5 4 4

2 3 6 5 1

3 1 4 1 3

2 3 3 5 3

*/

int N;

int GARO, SERO;

int map[102][102];

int chk[102][102];

typedef struct {

int posY;

int posX;

} _pos;

_pos POSITION[1000000];

void main()

{

int i, j;

scanf("%d", &N);

scanf("%d %d", &SERO, &GARO);

for (i = 1; i <= N; i++)

{

for (j = 1; j <= N; j++)

{

scanf("%d", &map[i][j]);

}

}

for (i = 1; i <= N; i++)

{

for (j = 1; j <= N; j++)

{

chk[i][j] = 0x7fffffff;

}

}

int head = 0, tail = 0;

for (i = 0; i <= N +1; i++)

{

for (j = 0; j <= N +1; j++)

{

if (chk[i][j] == 0)

{

POSITION[tail].posY = i;

POSITION[tail].posX = j;

tail++;

}

}

}

int Dy[] = { -1, 1, 0, 0 };

int Dx[] = { 0, 0, -1, 1 };

int temp;

while (1)

{

if (head == tail) break;

for (int dir = 0; dir < 4; dir++)

{

int tmpY = POSITION[head].posY + Dy[dir];

int tmpX = POSITION[head].posX + Dx[dir];

if (tmpY >= 1 && tmpX >= 1 && tmpY <= N && tmpX <= N)

{

temp = map[POSITION[head].posY][POSITION[head].posX] - map[tmpY][tmpX];

if (temp < 0) temp = temp * temp;

temp += chk[POSITION[head].posY][POSITION[head].posX];

if (chk[tmpY][tmpX] > temp)

{

chk[tmpY][tmpX] = temp;

POSITION[tail].posY = tmpY;

POSITION[tail].posX = tmpX;

tail++;

}

}

}

head++;

}

printf("%d", chk[SERO][GARO]);

}

#include<stdio.h>

/*

덧셈을 못하는 철수를 공부시키기 위해 자연수들을 주고, 그 중에 몇 개의 수를 골라서 그 합이 K가 될 수 있는지 알아보라고 시켰다.

철수 어머니가 자연수들을 무작위로 선택해서 본인도 가능한지 아닌지 모르고 있다. 어머니가 채점을 할 수 있게 주어진 문제의 답을 찾아주자.

번째 줄에 테스트 케이스 개수 T(1≤T≤10)가 주어진다.

두 번째 줄부터 아래 내용이 T개 만큼 주어진다.

첫 줄에 자연수 개수 N(5 <= N <= 20)과 K(1 <= K <= 2,000,000)가 공백으로 구분되어 입력된다.

다음 줄에 N개의 자연수 di(1 <= di <= 100,000)가 공백으로 구분되어 입력된다.

T줄에 걸쳐 각 테스트 케이스 별로 주어진 자연수 중 몇 개의 합이 K가 되면 “YES”를 아니면 “NO”를 출력한다.

입력 예시

2

5 19

1 2 4 7 10

5 25

1 2 4 7 10

출력 예시

YES

*/

#include<stdio.h>

int T;

int N;

int CNT;

int GOAL;

int num[100001];

int dfs(int pos, int cost)

{

if (cost > GOAL) return 0;

if (cost == GOAL) return 1;

for (int i = pos; i < N; i++) // 다중트리

{

if (dfs(i + 1, cost + num[i]) == 1) return 1;

}

return 0;

}

int dfs(int pos, int cost)

{

if (pos > cntN)  return 0;

if (cost > GOAL) return 0;

if (cost == GOAL) return 1;

if (dfs(pos + 1, cost + arr[pos]) == 1) return 1; // 이진트리

if ( dfs(pos + 1, cost )==1) return 1;

}

void main()

{

scanf("%d", &T);

while (T--)

{

scanf("%d %d", &N, &GOAL);

for (int i = 0; i < N; i++)

{

scanf("%d", &num[i]);

}

printf("%s\n", dfs(0, 0) == 1 ? "YES" : "NO");

}

}

#include<stdio.h>

typedef struct {

int sero;

int garo;

int idx;

int stat;

} _zergling;

하나로 모두 묶을 수 없기 때문에, 두가지를 동시에 사용해야 한다.

Zergling(가로,세로,idx)과 map(stat) 두개를 사용해서 처리

_zergling map[100][100];

_zergling Zergling[1000000];

int maps[100][100];

int cnt_time;

int Dx[] = { 0, 1, 0, -1 };

int Dy[] = { -1, 0, 1, 0 };

void main()

{

freopen("input.txt", "r", stdin);

int garo; int sero;

scanf("%d %d", &garo, &sero);

for (int i = 0; i < sero; i++)

{

for (int j = 0; j < garo; j++)

{

scanf("%1d", &map[i][j].stat);

maps[i][j] = map[i][j].stat;

if (map[i][j].stat == 1)

{

map[i][j].garo = j;

map[i][j].sero = i;

}

}

}

int zerg_garo = 0; 

int zerg_sero = 0;

scanf("%d %d", &zerg_garo, &zerg_sero);

int head = 0; int tail = 0;

map[zerg_sero - 1][zerg_garo - 1].stat = 0;

Zergling[tail].idx = 3;

Zergling[tail].garo = zerg_garo - 1;

Zergling[tail].sero = zerg_sero - 1;

cnt_time = map[zerg_sero - 1][zerg_garo - 1].idx;

tail++;

int a = 0;

while (1)

{

if (head == tail) break;

for (int dir = 0; dir < 4; dir++)

{

int garo_t = Zergling[head].garo + Dx[dir];

int sero_t = Zergling[head].sero + Dy[dir];

if (map[sero_t][garo_t].stat == 1)

{

a++;

map[sero_t][garo_t].stat = 0;

Zergling[tail].idx = Zergling[head].idx + 1;

Zergling[tail].garo = garo_t; // myqueue.push 의 다른 표현?

Zergling[tail].sero = sero_t;

cnt_time = (cnt_time > Zergling[tail].idx) ? cnt_time : Zergling[tail].idx;

tail++;

}

}

head++;

}

int cnt_num = 0;

for (int i = 0; i < sero; i++)

{

for (int j = 0; j < garo; j++)

{

scanf("%1d", &map[i][j].stat);

if (map[i][j].stat == 1)

{

cnt_num++;

}

}

}

printf("%d\n%d", Zergling[head - 1].idx, cnt_num);

}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=30&sfl=wr_subject

#include<stdio.h>

/*

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다.

이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이

몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면,

그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

efc6e5f9d670c6da62174cf11a66a8c2_1449731

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이

몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

[Copy] 5 7 3 0 2 4 4 1 1 2 5 4 0 6 2

[Copy] 3 1 7 13

*/

typedef struct {

int sX;

int sY;

int eX;

int eY;

} _pos;

_pos POS[1000];

int map[100][100] = { 0, };

int nCount = 0;

int nArea = 0;

int Area[100] = { 0, };

int sero;

int garo;

int idx = -1;

void find(int se, int ga)

{

nCount++;

if (se - 1 >= 0 && map[se - 1][ga] == 0) 

{

map[se - 1][ga] = idx;

find(se - 1, ga); 

}

if (se + 1 < sero && map[se + 1][ga] == 0)

{ 

map[se + 1][ga] = idx; 

find(se + 1, ga); 

}

if (ga - 1 >= 0 && map[se][ga - 1] == 0) 

{ 

map[se][ga - 1] = idx; 

find(se, ga - 1); 

}

if (ga + 1 < garo && map[se][ga + 1] == 0)

{ 

map[se][ga + 1] = idx;

find(se, ga + 1); 

}

//int Dy[] = { 1, 0,0, -1 };

//int Dx[] = { 0,-1, 1, 0 };

//nArea++;

//int head = 0;

//int tail = 1;

//while (1)

//{

// for (int x = 0; x < 4; x++)

// {

// int tmpX = garo + Dx[x];

// int tmpY = sero + Dy[x];

// if (map[tmpY][tmpX] == 0)

// {

// map[tmpY][tmpX] == -1;

// nCount++;

// }

// }

//}

}

void main()

{

int count;

// freopen("input.txt", "r", stdin);

scanf("%d %d %d", &sero, &garo, &count);

for (int i = 0; i < count; i++)

{

scanf("%d %d %d %d", &POS[i].sX, &POS[i].sY, &POS[i].eX, &POS[i].eY);

int tmpX = POS[i].eX - POS[i].sX;

int tmpY = POS[i].eY - POS[i].sY;

for (int y = POS[i].sY; y < tmpY + POS[i].sY; y++)

{

for (int x = POS[i].sX; x < tmpX + POS[i].sX; x++)

{

map[y][x]++;

}

}

}

for (int i = 0; i< sero; i++)

{

for (int j = 0; j < garo; j++)

{

if (map[i][j] == 0)

{

map[i][j] = --idx;

find(i, j);

Area[nArea++] = nCount;

nCount = 0;

}

}

}

for (int i = 0; i < nArea-1; i++)

{

for (int j = 0; j < nArea - 1 -i; j++)

{

if (Area[j] > Area[j + 1])

{

int tmp = Area[j];

Area[j] = Area[j + 1];

Area[j + 1] = tmp;

}

}

}

printf("%d\n", nArea);

for (int i = 0; i < nArea; i++)

{

printf("%d ", Area[i]);

}

}

BFS 

   소수경로 공부하기

   해밍경로

   경로 찾기 (http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1522&sca=3040)

   소수와 함께 하는 여행(http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=615&sca=3040)

   효율적인 해킹

   저글링 방사능 오염 (http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358%20&sca=3040)

백트래킹 

   해밀턴 순환회로(http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030#none)

   치즈 (http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1113&sca=3030)

   영역구하기(6/14 완료)

최단거리

   등산로찾기 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=391&sca=3070#none

기본적으로 이 문제는 두가지 방법으로 구할 수 있다.

1) 일단 L의 위치들을 다른곳에 각자 구한뒤 위치 차이 중 최대값으로 구할 것이냐

2) 각위치에서 가장 멀리 떨어져있는 애들의 위치 중 최대값으로 구할 것이냐

금번엔 2번으로 구했지만 1번으로 구해보고 싶음.

#include<stdio.h>

#include<memory.h>

/*

5 7

WLLWWWL

LLLWLLL

LWLWLWW

LWLWLLL

WLLWLWW

*/

char map[50][50];

int visited[50][50] = { 0 };

int max = 0;

int distance = 0;

int N, M;

typedef struct {

int row;

int col;

} _position;

_position point[2500];

int Dy[4] = { -1, 0, 1, 0 };

int Dx[4] = { 0, -1, 0, 1 };

int bfs(int row, int col)

{

int head, tail;

int max;

int i;

int tmp_row, tmp_col;

max = -1;

head = 0;

tail = 0;

memset(visited, -1, sizeof(visited)); // memory.h 나 string.h 를 못쓸때는 강제for문으로 변경해줘야함

memset(point, -1, sizeof(point)); // memory.h 나 string.h 를 못쓸때는 강제for문으로 변경해줘야함

point[tail].row = row;

point[tail].col = col;

visited[row][col] = 0;

tail++;

while (1)

{

if (head == tail) break;

for (i = 0; i < 4; i++) // 상 하 좌 우 

{

tmp_row = point[head].row + Dy[i];

tmp_col = point[head].col + Dx[i];

if (tmp_row >= 0 && tmp_row < N && tmp_col >= 0 && tmp_col < M) // MAP 범위 안에 존재

{

if (visited[tmp_row][tmp_col] == -1 && map[tmp_row][tmp_col] == 'L')

{

point[tail].row = tmp_row;

point[tail].col = tmp_col;

tail++;

visited[tmp_row][tmp_col] = visited[point[head].row][point[head].col] + 1; // 이전 위치보다 1칸 더 갔다는 뜻

// visited[tmp_row][tmp_col] = visited[tmp_row-Dy[i]][tmp_col-Dx[i]] + 1; 로 생각하는 게 더편함

if (visited[tmp_row][tmp_col] > max)

{

max = visited[tmp_row][tmp_col];

}

}

}

}

head++;

}

return max;

}

int main()

{

int i, j, k;

scanf("%d %d", &N, &M);

for (i = 0; i < N; i++)

{

scanf("%s", map[i]);

}

for (i = 0; i < N; i++)

{

for (j = 0; j < M; j++)

{

if (map[i][j] == 'L')

{

distance = bfs(i, j);

if (distance > max)

{

max = distance;

}

}

}

}

printf("%d\n", max);

}

//1번으로 구하는 것은 아래와 같음

//typedef struct {

// int sero;

// int garo;

//} _land;

//_land LAND[2500];

//_land POINT[250000];

//char map[50][50];

//int visited[50][50] = { 0, };

//

//int bfs(_land x, _land y)

//{

// memset(visited, -1, sizeof(visited));

// memset(POINT, -1, sizeof(POINT));

// int distance = 0;

// int head = 0;

// int tail = 0;

//

// int Dy[] = { -1,0,0,1 };

// int Dx[] = { 0 , -1, 1, 0 };

// int count = 0;

// while (head <= tail)

// {

// for (int i = 0; i < 4; i++)

// {

// int tmp_garo = Dx[i] + x.garo;

// int tmp_sero = Dy[i] + y.garo;

//

// if (tmp_sero == y.sero && tmp_garo == y.garo)

// {

// return count;

// }

// if (visited[tmp_sero][tmp_garo] == -1 && map[tmp_sero][tmp_garo] == 'L')

// {

// POINT[tail].garo = tmp_garo;

// POINT[tail].sero = tmp_sero;

// count++;

// tail++;

// }

// }

// head++;

// }

//

//}

//int main()

//{

// int sero;

// int garo;

//

//

// scanf("%d %d", &sero, &garo);

//

// for (int i = 0; i < sero; i++)

// {

// scanf("%s", map[i]);

// }

//

// // L의 위치 구하고, 배열에 넣기

// int idx = 0;

// for (int i = 0; i < sero; i++)

// {

// for (int j = 0; j < garo; j++)

// {

// if (map[i][j] == 'L')

// {

// LAND[idx].sero = i;

// LAND[idx].garo = j;

// idx++;

// }

// }

// }

// int max = 0; 

// int tmp = 0;

// // 이미 가로 세로 위치 구한 애들이고 L들로 구성된 애들임.

// for (int i = 0; i < idx; i++)

// {

// for (int j = 1; j < idx - 1; j++)

// {

// tmp = bfs(LAND[i], LAND[j]);

// if (max < tmp)

// {

// max = tmp;

// }

// }

// }

// printf("%d", max);

//}

/*

N×M장기판에 졸 한개와 말 한개가 놓여 있다.말의 이동 방향이 다음과 같다고 할 때, 말이 최소의 이동횟수로 졸을 잡으려고 한다.

말이 졸을 잡기 위한 최소 이동 횟수를 구하는 프로그램을 작성해보자.

첫 줄은 장기판 행의 수(N)와 열의 수(M)를 받는다.(1≤N, M≤100)

둘째 줄은 말이 있는 위치의 행(R), 열(C)의 수와 졸이 있는 위치의 행(S), 열(K)의 수를 입력받는다.

단, 장기판의 제일 왼쪽 위의 위치가(1, 1)이다.

각 행과 열은 R(1≤R≤N), C(1≤C≤M), S(1≤S≤N), K(1≤K≤M)이다.

말이 졸을 잡기 위한 최소 이동 횟수를 출력한다.

[Copy]

9 9

3 5 2 8

[Copy]

2

*/

#include <stdio.h>

typedef struct {

int sero;

int garo;

int idx;

} _position;

_position POSITION[1000000];

int  main()

{

int garo = 0; // 세로

int sero = 0; // 가로

int mal_sero = 0; // 말의 세로

int mal_garo = 0; // 말의 가로

int jol_sero = 0;

int jol_garo = 0;

scanf("%d %d", &sero, &garo);

scanf("%d %d", &mal_sero, &mal_garo);

scanf("%d %d", &jol_sero, &jol_garo);

int head = 0;

int tail = 1;

int Dy[] = { 2, 1, -1, -2, 2, 1, -1, -2 };

int Dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };

int map[102][102] = { 0, };

int tmp_sero = 0;

int tmp_garo = 0;

POSITION[0].sero = mal_sero;

POSITION[0].garo = mal_garo;

POSITION[0].idx = 0;

while (1)

{

for (int i = 0; i < 8; i++)

{

tmp_sero = POSITION[head].sero + Dy[i];

tmp_garo = POSITION[head].garo + Dx[i];

if (tmp_sero >= 1 && tmp_sero <= sero && tmp_garo >= 1 && tmp_garo <= garo)

{

if (map[tmp_sero][tmp_garo] == 0)

{

if (tmp_garo == jol_garo && tmp_sero == jol_sero)

{

printf("%d\n", POSITION[head].idx + 1);

return 0;

}

POSITION[tail].sero = tmp_sero;

POSITION[tail].garo = tmp_garo;

POSITION[tail].idx = POSITION[head].idx + 1;

tail++;

map[tmp_sero][tmp_garo] = 1;

}

}

}

head++;

}

return 0;

}

#include <iostream>

/*

입력 파일의 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다.

세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례 로 입력 파일의 둘째 줄부터 마지막 줄까지 주어진다.

치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어 지며 각 숫자 사이에는 빈칸이 하나씩 있다.

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출 력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

*/

//int M, N;

//int map[100][100];

//

//int time;

//int cnt_lastcheese;

//int cnt[100];

//void fill(int x, int y)

//{

// // 공기와 접촉된 칸만 녹임

// // c를 찾기

// if (x - 1 > 0) fill(x - 1, y);

// if (x + 1 < N) fill(x + 1, y);

// if (y - 1 > 0) fill(x, y - 1);

// if (y + 1 < N) fill(x, y + 1);

//}

//

//void main()

//{

// freopen("input.txt", "r", stdin);

// setbuf(stdout, NULL);

// scanf("%d %d", &M, &N);

// for (int i = 0; i < M; i++)

// {

// for (int j = 0; j < N; j++)

// {

// scanf("%d", &map[i][j]);

// if (map[i][j] == 1)

// {

// cnt[0]++;

// }

// }

// }

//

// //밖을 채우기

// fill();

// printf("%d", time);

// printf("%d", cnt_lastcheese);

//}

/*

1840 치즈 BFS로 풀기   정올 / 알고리즘

2012.08.05. 23:16

복사http ://blog.naver.com/hero1014/20163651496

번역하기

전용뷰어 보기

치즈

Time Limit : 1000MS

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색 으로 표시된 부분)가 놓여 있다.판의 가장자리(<그림 1>에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다.치 즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모 두 녹아 없어진다.그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모 두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 를 구하는 프로그램을 작성하시오.

입력 파일의 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다.세로와 가로의 길이는 최대 100이다.판의 각 가로줄의 모양이 윗 줄부터 차례 로 입력 파일의 둘째 줄부터 마지막 줄까지 주어진다.치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어 지며 각 숫자 사이에는 빈칸이 하나씩 있다.

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출 력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

13 12

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 1 0 0 0

0 1 1 1 0 0 0 1 1 0 0 0

0 1 1 1 1 1 1 0 0 0 0 0

0 1 1 1 1 1 0 1 1 0 0 0

0 1 1 1 1 0 0 1 1 0 0 0

0 0 1 1 0 0 0 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

3

5

*/

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

ifstream in("input.txt");

ofstream out("output.txt");

int min = 999;

int map[101][101] = { 0, };//치즈의 위치 입력 받기 위한 2차원 배열 

int tx[4000], ty[4000];//큐  3000은 작음 

int x[4] = { 0,0,1,-1 };

int y[4] = { 1,-1,0,0 };

int i, j;

int se, ga;//세로 가로의 길이 

in >> se >> ga;// input 첫째줄의 세로 가로길이 

for (i = 1; i <= se; i++)//세로 읽기

for (j = 1; j <= ga; j++)//가로 읽기

in >> map[i][j];//

int f = 1, s = 1;

tx[f] = 1;//큐 초기값 

ty[f] = 1;

int tempx, tempy;

int k;

int cnt;

for (cnt = 0;; cnt++)//치즈가 모두 녹아서 없어지는 데 걸리는 시간

{

f = 1; s = 1;

while (f <= s)// f,s 좌표를 중심으로 하상우좌 순서로 스캔 >> 스캔값 0이면 -1 그리고  >>s는 0의 갯수

{

printf("처음 while 시작 : f = %d , s = %d\n", f, s);

for (i = 0; i<4; i++)

{

tempx = tx[f] + x[i];// tx[1] + {0 0 1 -1}

tempy = ty[f] + y[i];// tx[1] + {1 -1 0 0} 

printf("\tif문 : i  = %d// tempx= %d ,  tempy =%d \n", i, tempx, tempy);

if (tempx > 0 && tempx <= se && tempy <= ga && tempy>0 && map[tempx][tempy] == 0)

{

s++;

tx[s] = tempx;

ty[s] = tempy;

map[tempx][tempy] = -1;//이미 읽은 큐는 -1로 바꿔줌

printf("\t****s증가 : %d //map[%d][%d]=0 ////%d\n", s, tempx, tempy, map[tempx][tempy]);

}

}

f++;

printf("f 증가 : %d ", f);

}

int q, l;

k = 0;

for (q = 1; q <= se; q++)//세로 서치

for (l = 1; l <= ga; l++)//가로 서치

{

if (map[q][l] == 1)//치즈 1인 값 찾음

{

f = 1, s = 1;

while (f <= s)

{

for (i = 0; i<4; i++)

{

tempx = q + x[i];

tempy = l + y[i];

if (tempx > 0 && tempx <= se && tempy <= ga && tempy > 0 && map[tempx][tempy] == -1)

{ 

map[q][l] = 0;

k++;

break;

}

}

f++;

}

}

}

if (k>0 && k<min)

min = k;

int m = 0;

int n = 0;

for (q = 1; q <= se; q++)

{

for (l = 1; l <= ga; l++)

{

if (map[q][l] == -1)

{

m++;

map[q][l] = 0;

}

}

if (m == (se*ga))

n = 1;

}

if (n == 1)

break;

}

out << cnt;//치즈가 모두 녹아서 없어지는 데 걸리는 시간

out << endl;//다음줄

out << min;//모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수

printf("%d , %d", cnt, min);

return 0;

}