그림판

당신은 그림판의 '색 채우기' 기능을 구현하려한다.

이미지 크기는 제한이 없다. (처리속도 < 3s)

입력 설명

가로 세로
색을 채우기 시작할 점 과 색
이미지의 색상 데이터

입력 예시

10 10
5 5 3
0000000000
0000001000
0000110100
0011000010
0100000010
0100000010
0100000100
0010001000
0001011000
0000100000

출력 예시

0000000000
0000001000
0000113100
0011333310
0133333310
0133333310
0133333100
0013331000
0001331000
0000100000
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

11개의 풀이가 있습니다. 1 / 2 Page

static void Main(string[] args)
        {
            int x = 5, y = 5, color = 3;
            int[,] Map = new int[10, 10]
            {
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,1,0,0,0},
                {0,0,0,0,1,1,0,1,0,0},
                {0,0,1,1,0,0,0,0,1,0},
                {0,1,0,0,0,0,0,0,1,0},
                {0,1,0,0,0,0,0,0,1,0},
                {0,1,0,0,0,0,0,1,0,0},
                {0,0,1,0,0,0,1,0,0,0},
                {0,0,0,1,0,1,1,0,0,0},
                {0,0,0,0,1,0,0,0,0,0}
            };


            DFS(new Point(x, y), ref Map,3);

            ShowMap(Map);


        }

        private static void ShowMap(int[,] map)
        {
            for (int x = 0; x < map.GetLength(0); x++)
            {
                for (int y = 0; y < map.GetLength(1); y++)
                {
                    Console.Write("{0}\t", map[x, y]);
                }
                Console.WriteLine();
            }
        }

        private static void DFS(Point pt, ref int[,] map,int colr)
        {
            int XMax = map.GetLength(0) - 1;
            int YMax = map.GetLength(1) - 1;

            map[pt.X, pt.Y] = colr;

            if (pt.X > 0 && map[pt.X - 1, pt.Y] == 0)
            {
                DFS(new Point(pt.X - 1, pt.Y), ref map,colr);
            }

            if (pt.X < XMax && map[pt.X + 1, pt.Y] == 0)
            {
                DFS(new Point(pt.X + 1, pt.Y), ref map, colr);
            }

            if (pt.Y > 0 && map[pt.X, pt.Y - 1] == 0)
            {
                DFS(new Point(pt.X, pt.Y - 1), ref map, colr);
            }

            if (pt.Y < YMax && map[pt.X, pt.Y + 1] == 0)
            {
                DFS(new Point(pt.X, pt.Y + 1), ref map, colr);
            }
        }
DFS는 깊이 우선탐색이기때문에, 이미지가 커질경우 재귀함수가 여러번 호출되어 스택 오버플로우가 발생합니다. - Steal, 2015/06/14 22:54 M D
헉, 다음 부터는 이런 문제에서는 BFS 를 사용하도록 하겠습니다 (_ _) - 허 빈, 2015/06/14 23:00 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

BFS로 구현했습니다.

python:

width, height = 10, 10
row, col, color = 5, 5, 3
map_ = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 1, 1, 0, 1, 0, 0],
        [0, 0, 1, 1, 0, 0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0, 0, 0, 0, 1, 0],
        [0, 1, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 1, 1, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]
queue = []


def bfs(coord, color):
    global map_, queue
    queue.append(coord)
    map_[coord[0]][coord[1]] = color
    while len(queue) != 0:
        front = queue.pop(0)
        for (drow, dcol) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            if (0 <= front[0]+drow < height and 0 <= front[1]+dcol < width) and map_[front[0]+drow][front[1]+dcol] == 0:
                queue.append((front[0]+drow, front[1]+dcol))
                map_[front[0]+drow][front[1]+dcol] = color


bfs((row, col), color)

for i in range(height):
    for j in range(width):
        print(map_[i][j], end='')
    print('')
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
void fill(int x,int y,int color,int target, char ***img)
{
    if (((*img)[y][x] - '0') == target)
    {
        (*img)[y][x] = color + '0';

        fill(x + 1, y, color, target, img);
        if (x > 0)
            fill(x -1, y, color, target, img);
        fill(x, y+1, color, target, img);
        if (y > 0)
            fill(x, y-1, color, target, img);
    }
}

void exce89()
{
    int x, y;
    int start[2];
    int color,target=0;
    char **img;
    char flush;


    FILE *f;
    fopen_s(&f, "input89.dat", "r");

    fscanf_s(f, "%d %d", &x,&y);
    fscanf_s(f, "%d %d %d", &start[0], &start[1], &color);

    img = (char **)malloc(sizeof(char) * y);
    fscanf_s(f, "%c", &flush);

    for (int i = 0; i < y; i++)
    {
        img[i] = (char *)malloc(sizeof(char) * (2 * x));
        fgets(img[i], 2 * x, f);
    }
    target = (img[start[1]][start[0]] - '0');

    fill(start[0], start[1], color, target, &img);

    for (int i = 0; i < y; i++)
    {
        printf("%s", img[i]);
    }

    fclose(f);

}

C로 작성해봤습니다. 입력은 커맨드 창에서 하기엔 양이 너무 많아서 파일 입력으로 처리했습니다. 근데 예제문제에 밑에 구멍이 하나 있네요...자꾸 새어나가서 어디서 에러났나 한참 찾았네요.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

자바로 작성해봤습니다.

package codingDoJang;

public class DrawingBoard {

    public static void main(String[] args) {

        // board 
        int board[][] = 
            {  
                    {0,0,0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,1,0,0,0},
                    {0,0,0,0,1,1,0,1,0,0},
                    {0,0,1,1,0,0,0,0,1,0},
                    {0,1,0,0,0,0,0,0,1,0},
                    {0,1,0,0,0,0,0,0,1,0},
                    {0,1,0,0,0,0,0,1,0,0},
                    {0,0,1,0,0,0,1,0,0,0},
                    {0,0,0,1,0,1,1,0,0,0},
                    {0,0,0,0,0,0,0,0,0,0} 
            };

        // start point
        int x = 5, y = 5;

        // color
        int changeColor = 3;
        int beforeColor = board[x][y];

        fill(board, x, y, beforeColor, changeColor);

        print(board);
    }

    private static void fill(int board[][], int x, int y, int beforeColor, int changeColor) {

        // 기저사례

        if (board[x][y] == beforeColor) 
            board[x][y] = changeColor;
        else return;

        if (x-1 != -1)  fill(board, x-1, y, beforeColor, changeColor);
        if (x+1 != board.length) fill(board, x+1, y, beforeColor, changeColor);
        if (y-1 != -1) fill(board, x, y-1, beforeColor, changeColor);
        if (y+1 != board.length) fill(board, x, y+1, beforeColor, changeColor);
    }

    private static void print(int board[][]) {

        // 정사각형이라 가정
        int width = board.length, height = board.length;

        for (int x = 0 ; x < width ; x++) {
            for (int y = 0 ; y < height ; y++)
                System.out.print(board[x][y]);
            System.out.println();
        }

    }
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
        public static void Answer()
        {

            var x = 5;
            var y = 5;
            var color = 3;
            int[,] board = new int[10, 10]
            {
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,1,0,0,0},
                {0,0,0,0,1,1,0,1,0,0},
                {0,0,1,1,0,0,0,0,1,0},
                {0,1,0,0,0,0,0,0,1,0},
                {0,1,0,0,0,0,0,0,1,0},
                {0,1,0,0,0,0,0,1,0,0},
                {0,0,1,0,0,0,1,0,0,0},
                {0,0,0,1,0,1,1,0,0,0},
                {0,0,0,0,1,0,0,0,0,0}
            };

            Search(board, x, y, board[x, y], color);
            Display(board);

        }

        private static void Search(int[,] board, int x, int y, int prev, int color)
        {
            if (board[x, y] == prev) board[x, y] = color;
            else return;

            if (x - 1 >= 0) Search(board, x - 1, y, prev, color);
            if (x + 1 < board.Length) Search(board, x + 1, y, prev, color);
            if (y - 1 >= 0) Search(board, x, y - 1, prev, color);
            if (y + 1 < board.Length) Search(board, x, y + 1, prev, color);
        }

        private static void Display(int[,] board)
        {
            for (int x = 0; x < board.GetLength(0); x++)
            {
                for (int y = 0; y < board.GetLength(1); y++)
                    Console.Write("{0}\t", board[x, y]);
                Console.WriteLine();
            }
        }
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def paint(map,from_x,from_y,prev=0):
    if prev==0:
        if map[from_x][from_y]==0:
            map[from_x][from_y]=3
            paint(map,from_x-1  ,from_y     ,1)
            paint(map,from_x    ,from_y-1   ,2)
            paint(map,from_x+1  ,from_y     ,3)
            paint(map,from_x    ,from_y+1   ,4)

    elif prev==1:
        if map[from_x][from_y]==0:
            map[from_x][from_y]=3
            paint(map,from_x-1  ,from_y     ,1)
            paint(map,from_x    ,from_y-1   ,2)
            paint(map,from_x    ,from_y+1   ,4)

    elif prev==2:
        if map[from_x][from_y]==0:
            map[from_x][from_y]=3
            paint(map,from_x-1  ,from_y     ,1)
            paint(map,from_x    ,from_y-1   ,2)
            paint(map,from_x+1  ,from_y     ,3)

    elif prev==3:
        if map[from_x][from_y]==0:
            map[from_x][from_y]=3
            paint(map,from_x    ,from_y-1   ,2)
            paint(map,from_x+1  ,from_y     ,3)
            paint(map,from_x    ,from_y+1   ,4)

    elif prev==4:
        if map[from_x][from_y]==0:
            map[from_x][from_y]=3
            paint(map,from_x-1  ,from_y     ,1)
            paint(map,from_x+1  ,from_y     ,3)
            paint(map,from_x    ,from_y+1   ,4)

주석은 없어서 말로 풀이합니다. prev는 이전 좌표 이동을 나타내는 겁니다. 따로 값을 안주면 0이 되도록 설정되 있습니다. 1은 좌,2는 상,3은 우,4는 하 이런식으로 지난 번 함수가 현재 좌표(from_x,from_y)가 어디에서 온 것인지 알기 위한 것입니다. prev는 없어도 되지만 약간이나마 재귀를 줄여보고자 사용되었습니다. 한번 재귀를 할때마다 처음을 제외라곤 상,좌,우 ,하 방향중 3개를 선택해 이동해서 만약 그곳에 0이 있다면 3으로 바꾸는 방법을 사용했습니다.

재귀로 사실 prev도 필요없고 함수안에 밑에 것만 있어도 작동하지만 그래도 약간이나마 중복을 줄여보고자 했습니다.

paint(map,from_x-1  ,from_y     ,1)
paint(map,from_x    ,from_y-1   ,2)
paint(map,from_x+1  ,from_y     ,3)
paint(map,from_x    ,from_y+1   ,4)

다 풀고 보니 색상도 선택 가능해야 하군요;; 그건 간단한 편이니 패스

ps.8:8 맵에 6.818771362304688e-05걸렸습니다 약 0.00006초

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
$board = array(
        array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
        array(0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
        array(0, 0, 0, 0, 1, 1, 0, 1, 0, 0),
        array(0, 0, 1, 1, 0, 0, 0, 0, 1, 0),
        array(0, 1, 0, 0, 0, 0, 0, 0, 1, 0),
        array(0, 1, 0, 0, 0, 0, 0, 0, 1, 0),
        array(0, 1, 0, 0, 0, 0, 0, 1, 0, 0),
        array(0, 0, 1, 0, 0, 0, 1, 0, 0, 0),
        array(0, 0, 0, 1, 0, 1, 1, 0, 0, 0),
        array(0, 0, 0, 0, 1, 0, 0, 0, 0, 0));
$x = 5;
$y = 5;
$color = 3;
$pre_color = $board[$x][$y];

echo "* Org img <br>";
draw($board);

// fill Color
fill($board, $x, $y, $color, $pre_color);

echo "<br>* Filled img <br>";
draw($board);

function fill(&$canv, $x, $y, $color, $pre_color) {
    if ($canv[$x][$y] == $pre_color) {
        $canv[$x][$y] = $color;
    } else {
        return;
    }
    if ($x - 1 > 0) fill($canv, $x - 1, $y, $color, $pre_color);
    if ($x + 1 > 0) fill($canv, $x + 1, $y, $color, $pre_color);
    if ($y - 1 > 0) fill($canv, $x, $y - 1, $color, $pre_color);
    if ($y + 1 > 0) fill($canv, $x, $y + 1, $color, $pre_color);
}
function draw($img) {
    foreach ($img as $arr) {
        foreach ($arr as $v) {
            echo $v;
        }
        echo "<br/>";
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

큐를 이용했습니다. 큐에서 점 하나 꺼내서 색칠하고 그 점 주변에 칠해야 되는 점 찾아서 큐에 넣는 과정을 큐가 빌때까지 반복합니다.

col,row =map(int, raw_input().split())
x,y,c = map(int, raw_input().split())
p = [map(int, list(raw_input())) for i in range(row)]

def paint(p,x,y,c):
    prev_c = p[y][x]
    q = [(y,x)]
    while q:
        yy,xx=q.pop(0)
        p[yy][xx]=c
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,+1)]:
            if yy+dy in range(len(p)) and xx+dx in range(len(p[0])) and\
                p[yy+dy][xx+dx]==prev_c:
                q.append((yy+dy, xx+dx))
def display(p):
    for line in p: print ''.join(str(x) for x in line)

paint(p,x,y,c)
print
display(p)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬입니다. BFS로 풀었습니다.

def do(s, x, y, c):
    def offsets(p):
        x, y = p
        result = [(x+a, y+b) for (a, b) in [(-1, 0), (1, 0), (0, -1), (0, 1)]
                   if (0 <= (x+a) < w) and (0 <= y + b < h)]
        return result

    data = list(s.replace('\n', ''))
    c = str(c)
    if data[x + y * w] == '0':
        temp = [(x, y)]
        while temp:
            a, b = temp.pop()
            if data[a + b * w] == '0':
                data[a + b * w] = c
                for i, j in offsets((a, b)):
                    if data[i + j * w] == '0':
                        temp.append((i, j))
    result = '\n'.join(''.join(data[x*w:(x+1)*w]) for x in range(h))
    print(result)


sample = """\
0000000000
0000001000
0000110100
0011000010
0100000010
0100000010
0100000100
0010001000
0001001000
0000110000"""
x, y, c = 5, 5, 3
do(sample, x-1, y-1, c)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
data = list(list(int(j) for j in i) for i in '''0000000000
0000001000
0000110100
0011000010
0100000010
0100000010
0100000100
0010001000
0001011000
0000100000'''.split('\n'))
class area:
    def __init__(self, target):
        self.target, self.color_from, self.dic = (target, 0, {})
    def infest(self, x, y):
        if self.dic == {}:
            self.color_from = self.target[y][x]
        self.dic[(x, y)] = True
        temp = []
        for dx, dy in [(1, 0),(-1, 0),(0, 1),(0, -1)]:
            i, j = x+dx, y+dy
            if all((0 <= i < len(self.target[0]),
             0 <= j < len(self.target),
             (i, j) not in self.dic,
             self.target[j][i] == self.color_from)):
                temp.append((x+dx, y+dy))
        pr = []
        if temp:
            for i, j in temp:
                if  self.target[j][i] == self.color_from:
                    self.infest(i, j)

def fill(li, x, y, color):
    a = area(li)
    a.infest(x, y)
    for i, j in a.dic.keys():
        li[j][i] = color

while __name__ == '__main__':
#    length, height = list(map(int, input('>>>').split()))
    x, y, color = list(map(int, input('>>>').split()))
#    data = list(list(int(numchar) for numchar in input('>>>>>>')) for h in range(height))
    fill(data, x, y, color)
    for i in data:
        print(''.join(str(j) for j in i))

재귀함수 이용하였습니다. 파이썬 3.5.1

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 11
cs x 2
python x 5
cpp x 1
java x 1
php x 1
ruby x 1