글 읽기 - 1987번 알파벳 문제요 ㅠㅠ

wwiiiii 9년 전 0

DFS로 푸는 문제라 생각해서 그렇게 짰는데...어디가 틀렸는지를 모르겠네요 ㅠ

알파벳을 방문했는지 배열을 used1로, 그 좌표를 방문했는지를 visited1[][]로 잡고 dfs 재귀로 짰는데 왜 틀렸는지를 모르겠어요 ㅠㅠ

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char dx[4]={0,0,1,-1};
char dy[4]={1,-1,0,0};
char arr[22][22];//arr[R][C]
typedef pair<int,int> P;
int M,R,C;

void input()
{
	scanf("%d %d",&R,&C);
	for(int i=1;i<=R;i++)
	{
		for(int j=1;j<=C;j++)
		{
			do{
			scanf("%c",&arr[i][j]);
			}while(!('A'<=arr[i][j]&&arr[i][j]<='Z'));//\n처리용
		}
	}
}

void dfs(bool used1[], bool visited1[][22], P start, int score)
{
	if(used1[arr[start.first][start.second]] == true || visited1[start.first][start.second]==true) return;
    //알파벳이 사용됐거나 방문한 좌표면
	used1[arr[start.first][start.second]] = true;
	visited1[start.first][start.second] = true;
	score++;
	if(M<score) M=score;//최대 경로 길이 갱신
	for(int i=0;i<4;i++)
	{
		P next;
		next.first = start.first + dx[i];
		next.second = start.second + dy[i];
		if (!(1<=next.first && next.first<=R && 1<=next.second && next.second<=C)) continue;
        //칸 범위를 벗어나는 경우
		dfs(used1,visited1,next,score);
	}
}

int main()
{
	bool used['Z'+2]={};
	bool visited[22][22]={};
	input();
	dfs(used,visited,make_pair(1,1),0);
	printf("%d",M);
}

h0ngjun7 9년 전 0

몇 가지 말씀드리고 싶은 게 있는데

1) " %c"(띄워쓰기 + %c)를 쓰시면 자동으로 줄바꿈이나 띄워쓰기는 걸러서 읽어들일 수 있습니다.

2) used 배열만 사용하셔도 됩니다.

3) 재귀호출하는 부분에서 used에 값을 true로 갱신시켜주셨는데, false로 초기화시켜주는 부분이 필요합니다.

h0ngjun7 9년 전 0

아래는 제 소스코드입니다.

#include <stdio.h>
int n, m, res = 1, chk[26];
char S[22][22];
int px[4]={1,-1,0,0};
int py[4]={0,0,1,-1};
void go(int x, int y, int k) {
    if (k > res) res = k;
    int nx, ny;
    for (int i = 0; i < 4; i++) {
        nx = x+px[i]; ny = y+py[i];
        if (0<=nx && nx<n && 0<=ny && ny<m) {
            if (chk[S[nx][ny]-'A'] == 0) {
                chk[S[nx][ny]-'A'] = 1;
                go(nx, ny, k+1);
                chk[S[nx][ny]-'A'] = 0;
            }
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 0; i < n; i++) scanf("%s",S[i]);
    chk[S[0][0]-'A'] = 1;
    go(0,0,1);
    printf("%d",res);
    return 0;
}

wonjung1618 6년 전 0

제 소스인데 틀렸따고 해요 appa님과 비슷한데 어디가 문제일까요?? 도와주시면 감사하겠습니다.

#include <stdio.h>

int R, C;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
char map[22][22];
int max;

void back(int x, int y, int d, int c[100]) 
{
	int i;
	int X, Y;

	if (d > max) {
		max = d;
	}

	for (i = 0; i < 4; i++) {
		X = x + dx[i]; Y = y + dy[i];

		if (X >= 0 && X < R && Y >= 0 && Y < C && c[map[X][Y]]!=1) {
			c[map[X][Y]] = 1;
			back(X, Y, d + 1, c);
			c[map[X][Y]] = 0;
		}

	}
}


int main(void)
{
	char str[22];
	int i, j;
	int chk[100];

	for (i = 0; i < 100; i++) {
		chk[i] = 0;
	}

	scanf("%d %d", &R, &C);

	for (i = 0; i < R; i++) {
		scanf("%s", str);
		for (j = 0; j < C; j++) {
			map[i][j] = str[j];
		}
	}

	chk[map[0][0]] = 1;

	back(0, 0, 1, chk);

	printf("%d", max);

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1987번 알파벳 문제요 ㅠㅠ

wwiiiii 9년 전 0

h0ngjun7 9년 전 0

h0ngjun7 9년 전 0

wonjung1618 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말