당신은 그림판의 '색 채우기' 기능을 구현하려한다.
이미지 크기는 제한이 없다. (처리속도 < 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
28개의 풀이가 있습니다.
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);
}
}
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
Ruby
BFS로 풀었습니다.
paint_image = proc do
xy, start = (1..2).map { gets.split.map(&:to_i) }
image = Matrix[*(1..xy[0]).map { gets.chars[0, xy[1]] }]
q, find_color, paint = [start[0,2]], image[*start[0,2]].to_s, start[2].to_s
cell = ->x,y { x>=0 && y>=0 && image[x,y] == find_color }
next_of = ->x,y { [[1,0],[-1,0],[0,-1],[0,1]].map {|r,c| [x+r,y+c] }.select &cell }
nexts = ->x,y { image.send(:[]=, x, y, paint); next_of[x,y] }
q += nexts[*q.shift] until !q[0]
puts image.to_a.map(&:join)
end
Test
$stdin = StringIO.new("10 10\n" +
"5 5 3\n" +
"0000000000\n" +
"0000001000\n" +
"0000110100\n" +
"0011000010\n" +
"0100000010\n" +
"0100000010\n" +
"0100000100\n" +
"0010001000\n" +
"0001011000\n" +
"0000100000\n")
expect { paint_image[] }.to output("0000000000\n" +
"0000001000\n" +
"0000113100\n" +
"0011333310\n" +
"0133333310\n" +
"0133333310\n" +
"0133333100\n" +
"0013331000\n" +
"0001311000\n" +
"0000100000\n").to_stdout
메소드 순환 호출을 이용해 작성했습니다.
// 그림판 - C#
using System;
namespace Ppaint
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("캔버스 크기를 입력하세요.");
string select = Console.ReadLine();
int x = int.Parse(select.Split(' ')[0]);
int y = int.Parse(select.Split(' ')[1]);
Console.WriteLine("색을 채우기 위해 찍을 점과 색을 입력하세요.");
select = Console.ReadLine();
int ptnx = int.Parse(select.Split(' ')[0]);
int ptny = int.Parse(select.Split(' ')[1]);
int color = int.Parse(select.Split(' ')[2]);
Console.WriteLine("현재 캔버스 상태를 그려주세요.");
int[,] canvas = new int[y, x];
for (int i = 0; i < y; i++)
{
for (int j = 0; j < x; j++)
canvas[i, j] = int.Parse(char.ToString(Console.ReadKey().KeyChar));
Console.WriteLine();
}
Console.WriteLine("결과는 다음과 같습니다.");
int temp = canvas[ptny, ptnx];
Pill(ptnx, ptny, canvas, canvas[ptny, ptnx], color);
for (int i = 0; i < y; i++)
{
for (int j = 0; j < x; j++)
Console.Write(canvas[i, j]);
Console.WriteLine();
}
}
static void Pill(int x, int y, int[,] canvas, int temp, int color)
{
try
{
if (canvas[y, x] != temp)
return;
}
catch { return; }
canvas[y, x] = color;
Pill(x + 1, y, canvas, temp, color);
Pill(x, y + 1, canvas, temp, color);
Pill(x - 1, y, canvas, temp, color);
Pill(x, y - 1, canvas, temp, color);
}
}
}
// 술취한 바퀴벌레(Random walk) - C#
using System;
namespace DrunkRoach
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("격자의 가로, 세로, 바퀴벌레의 초기 위치를 입력하세요.");
string select = Console.ReadLine();
int x = int.Parse(select.Split(' ')[0]);
int y = int.Parse(select.Split(' ')[1]);
int defx = int.Parse(select.Split(' ')[2]) - 1;
int defy = int.Parse(select.Split(' ')[3]) - 1;
int counter = 0; int[,] board = new int[y, x];
Random r = new Random();
for (int i = 0; i < y; i++)
for (int j = 0; j < x; j++)
board[i, j] = 0;
NO:
int addx = 0, addy = 0;
try
{
addx = r.Next(-1, 2);
addy = r.Next(-1, 2);
defx += addx; defy += addy;
board[defy, defx]++;
}
catch { defx -= addx; defy -= addy; goto NO; }
counter++;
for (int i = 0; i < y; i++)
for (int j = 0; j < x; j++)
if (board[i, j] == 0)
goto NO;
Console.WriteLine("결과:");
for (int i = 0; i < y; i++)
{
for (int j = 0; j < x; j++)
Console.Write("{0} ", board[i, j]);
Console.WriteLine();
}
Console.WriteLine("총 이동 횟수: {0}", counter);
}
}
}
javascript
BFS 로 구현하였습니다.
visited 배열을 따로 만들어서 큐에 넣기 전 이미 큐에 들어간 좌표인지를 검사합니다.
무조건 큐에 넣고 색칠하기 전 색칠했는지/안했는지를 검사할 수도 있으나
그렇게 하면 필요없는 데이타가 큐에 들어가기 때문입니다.
var paint = function(canvas, x, y, c) {
var queue = [];
var visited = Array.from(Array(canvas.length), v => Array.from(Array(canvas[0].length), () => 0));
enqueue(queue, [x, y, c], canvas, visited);
while (queue.length > 0) {
var [row, col, color] = queue.shift();
canvas[row][col] = color;
enqueue(queue, [row - 1, col, c], canvas, visited);
enqueue(queue, [row + 1, col, c], canvas, visited);
enqueue(queue, [row, col + 1, c], canvas, visited);
enqueue(queue, [row, col - 1, c], canvas, visited);
}
};
var enqueue = function(queue, [row, col, color], canvas, visited) {
if (canvas[row] && canvas[row][col] === 0 && visited[row][col] !== 1) {
queue.push([row, col, color]);
visited[row][col] = 1;
}
};
var print = function(canvas) {
console.log(canvas.map(v => v.join("")).join("\n"));
};
var input=
`10 10
5 5 3
0000000000
0000001000
0000110100
0011000010
0100000010
0100000010
0100000100
0010001000
0001011000
0000100000`;
var lines = input.split("\n");
var [m, n] = lines[0].split(" ");
var [x0, y0, c0] = lines[1].split(" ").map(v => parseInt(v));
var map = lines.slice(2).map(v => v.split("").map(v => parseInt(v)));
paint(map, x0, y0, c0);
print(map);
C#: BFS
외벽(-1)을 두르고 시작합니다. 초기화 코드는 귀찮아서 생략..
class Location
{
public int x { get; set; }
public int y { get; set; }
public Location(int x, int y)
{
this.x = x;
this.y = y;
}
public Location[] neighbors()
{
return new Location[4]
{
new Location(x-1, y),
new Location(x+1, y),
new Location(x, y-1),
new Location(x, y+1)
};
}
}
class ContactList
{
static void Main(string[] args)
{
int color = 3;
int[,] image = new int[12, 12]
{
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
{-1, 0,0,0,0,0,0,0,0,0,0, -1},
{-1, 0,0,0,0,0,0,1,0,0,0, -1},
{-1, 0,0,0,0,1,1,0,1,0,0, -1},
{-1, 0,0,1,1,0,0,0,0,1,0, -1},
{-1, 0,1,0,0,0,0,0,0,1,0, -1},
{-1, 0,1,0,0,0,0,0,0,1,0, -1},
{-1, 0,1,0,0,0,0,0,1,0,0, -1},
{-1, 0,0,1,0,0,0,1,0,0,0, -1},
{-1, 0,0,0,1,0,1,1,0,0,0, -1},
{-1, 0,0,0,0,1,0,0,0,0,0, -1},
{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
};
Queue<Location> que = new Queue<Location>();
que.Enqueue(new Location(5, 5));
while (que.Count > 0)
{
Location cur = que.Dequeue();
foreach (var loc in cur.neighbors())
{
if (image[loc.x, loc.y] == 0)
{
image[loc.x, loc.y] = color;
que.Enqueue(loc);
}
}
}
for (int i = 1; i <= 10; i++)
{
for (int j = 1; j <= 10; j++)
{
Write(image[i, j]);
}
WriteLine();
}
}
}
파이썬 3.6
"""
아이디어>
1) 시작점을 기준으로 주변에 색이 채워지지 않은 테두리 범위를 찾고,
2) 시작점이 테두리 안에 있으면 테두리 안으로,시작점이 테두리 밖에 있으면 테두리 밖으로 색이 없는 위치에 지정된 색 데이터를 채웁니다.
"""
def inputdata():
size = input('').split()
info = input('').split()
image = [list(input('')) for i in range(int(size[0]))]
data = [size,info,image]
return data
def painting(data):
outline_start,tmp,border = [],[],[]
for i,value_i in enumerate(data[2]):
for h,value_h in enumerate(value_i):
if value_h == '1':
outline_start.extend([i,h])
# 시작할 점이 테두리 안
if outline_start[0] < int(data[1][0]) and data[2][int(data[1][0])].index('1') < int(data[1][1]):
for i in data[2]:
if i.count('1') >= 2:
for g,p in enumerate(i):
if p == '1':
tmp.append(g)
border = [min(tmp),max(tmp)]
for j in range(border[0],border[1]+1):
if i[j] != '1':
i[j] = data[1][2]
tmp = []
# 시작할 점이 테두리 밖
else:
for i in data[2]:
if i.count('1') <= 1:
for g,p in enumerate(i):
if p != '1':
i[g] = data[1][2]
if i.count('1') >= 2:
for g,p in enumerate(i):
if p == '1':
tmp.append(g)
border = [min(tmp),max(tmp)]
for j in range(border[0]):
i[j] = data[1][2]
for j in range(border[1]+1,len(i)):
i[j] = data[1][2]
tmp = []
print("\n")
for i in data[2]:
print(''.join(i))
if __name__ == "__main__":
data = inputdata()
painting(data)
*결과값
10 10
5 5 3
0000000000
0000001000
0000110100
0011000010
0100000010
0100000010
0100000100
0010001000
0001011000
0000100000
0000000000
0000001000
0000113100
0011333310
0133333310
0133333310
0133333100
0013331000
0001311000
0000100000
1로 구성된 테두리가 오목도형을 이루는 경우와, 테두리가 중간에 열려있는경우 바깥도 칠해지게 만들어보았습니다.
import copy
def paint(a, m, k):
def xexpand(a, m):
result = set()
i = 0
while i <= m[1]:
if a[m[0]][m[1]-i]:
break
result.add((m[0], m[1]-i))
i += 1
i = 0
while m[1]+i <= len(a[0])-1:
if a[m[0]][m[1]+i]:
break
result.add((m[0], m[1]+i))
i += 1
return result
def yexpand(a, m):
if not(a[m[0]][m[1]]):
result = {(m[0], m[1])}
if m[0]:
if not(a[m[0]-1][m[1]]):
result.add((m[0]-1, m[1]))
if len(a) - m[0]-1:
if not(a[m[0]+1][m[1]]):
result.add((m[0]+1, m[1]))
return result
else:
return set()
def connected(a, m):
result = {(m[0], m[1])}
last = {(m[0], m[1])}
record = [set(), {(m[0], m[1])}]
while 1:
for i in last:
result.update(xexpand(a, i))
record.append(copy.deepcopy(result))
last = record[-1] - record[-3]
for i in last:
result.update(yexpand(a, i))
record.append(copy.deepcopy(result))
last = record[-1] - record[-3]
if record[-1] == record[-3]:
break
return result
for i in connected(a, m):
a[i[0]][i[1]] = k
return a
Swift입니다.
재귀호출로 풀었습니다.
import Foundation
var testPicture = [
[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]]
func printBoard(_ board:[[Int]]) {
for line in board {
print(line.reduce("", {$0 + String($1) + " "}))
}
}
func fillColor(_ givenBoard: [[Int]], _ x: Int, _ y: Int, _ color: Int) -> [[Int]] {
var board = givenBoard
let targetColor = board[y][x]
board[y][x] = color
if x > 0 && board[y][x-1] == targetColor {
board = fillColor(board, x - 1, y, color)
}
if x < (board[y].count - 1) && board[y][x + 1] == targetColor {
board = fillColor(board, x + 1, y, color)
}
if y > 0 && board[y - 1][x] == targetColor {
board = fillColor(board, x, y - 1, color)
}
if y < (board[y].count - 1) && board[y + 1][x] == targetColor {
board = fillColor(board, x, y + 1, color)
}
return board
}
printBoard( fillColor(testPicture, 5, 5, 3) )
결과는...
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 3 1 0 0
0 0 1 1 3 3 3 3 1 0
0 1 3 3 3 3 3 3 1 0
0 1 3 3 3 3 3 3 1 0
0 1 3 3 3 3 3 1 0 0
0 0 1 3 3 3 1 0 0 0
0 0 0 1 3 1 1 0 0 0
0 0 0 0 1 0 0 0 0 0
val arr = Array(
"0000000000".toCharArray,
"0000001000".toCharArray,
"0000110100".toCharArray,
"0011000010".toCharArray,
"0100000010".toCharArray,
"0100000010".toCharArray,
"0100000100".toCharArray,
"0010001000".toCharArray,
"0001011000".toCharArray,
"0000100000".toCharArray
)
val (x, y) = (5, 3)
val fromColor = arr(x)(y)
val toColor = '3'
val direction = List((1, 0), (0 ,1), (-1, 0), (0, -1))
def fillColor(N:Int, M:Int){
println(N, M)
if(N < 0 || N >= 10 || M < 0 || M >= 10 || arr(N)(M) != fromColor) ()
else{
arr(N)(M) = toColor
for((a, b) <- direction){
fillColor(N + a, M + b)
}
}
}
fillColor(5, 3)
arr.map(_.toList).toList.foreach(v => println(v.mkString(" ")))
board = [[int(q) for q in p] for p in '''0000000000
0000001000
0000110100
0011000010
0100000010
0100000010
0100000100
0010001000
0001011000
0000100000'''.split('\n')]
orgcolor = ''
def coloring(x, y, color):
global orgcolor, board
if orgcolor == '': orgcolor = board[y - 1][x - 1]
if board[y - 1][x - 1] == orgcolor:
board[y - 1][x - 1] = color
coloring(x, y + 1, color)
coloring(x, y - 1, color)
coloring(x + 1, y, color)
coloring(x - 1, y, color)
coloring(5, 5, 3)
for mainprt in board:
for prt in mainprt:
print(prt, end='')
print()
Python 3입니다
자신을 색칠한 뒤 재귀함수를 이용하여 자신의 상하좌우에 있는 숫자를 변경하는 방식입니다
위의 입력 예시 그대로 복붙하면 출력 예시와 동일하게 출력됩니다. 숫자 바꿔도 잘 됩니다. 재귀함수로 풀었습니다.
import java.util.Scanner;
public class PaintFill {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[][] data = new int[sc.nextInt()][sc.nextInt()];
int xpos = sc.nextInt(), ypos = sc.nextInt(), color = Integer.valueOf(sc.nextLine().trim());
for (int i = 0; i < data.length; i++) {
String[] temp = sc.nextLine().split("");
for (int j = 0; j < data[0].length; j++)
data[i][j] = Integer.valueOf(temp[j]);
}
FillColor(data, xpos, ypos, color, data[xpos][ypos]);
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++)
System.out.print(data[i][j]);
System.out.println();
}
System.out.println();
}
private static void FillColor(int[][] data, int xpos, int ypos, int color, int OldColor) {
if (data[xpos][ypos] == OldColor)
data[xpos][ypos] = color;
if (xpos - 1 > -1 && data[xpos - 1][ypos] == OldColor)
FillColor(data, xpos - 1, ypos, color, OldColor);
if (xpos + 1 < data.length && data[xpos + 1][ypos] == OldColor)
FillColor(data, xpos + 1, ypos, color, OldColor);
if (ypos - 1 > -1 && data[xpos][ypos - 1] == OldColor)
FillColor(data, xpos, ypos - 1, color, OldColor);
if (ypos + 1 < data[0].length && data[xpos][ypos + 1] == OldColor)
FillColor(data, xpos, ypos + 1, color, OldColor);
}
}
def paint(mat,x,y,color):
dr = ((1,0),(0,1),(-1,0),(0,-1))
qu = [(x,y)]
oc = mat[x][y]
if oc == color: return
mat[x][y] = color
while qu:
i,j = qu.pop(0)
for dx,dy in dr:
if 0<=i+dx<len(mat) and 0<=j+dy<len(mat[0]) and mat[i+dx][j+dy] == oc:
mat[i+dx][j+dy] = color
qu.append((i+dx,j+dy))
return
sample = '''\
0000000000
0000001000
0000110100
0011000010
0100000010
0100000010
0100000100
0010001000
0001011000
0000100000'''
sp = [[int(j) for j in i] for i in sample.split('\n')]
val = [int(i) for i in input('x y clolr: ').split()]
paint(sp,*val)
for i in range(10):
for j in range(10):
print(sp[i][j],end='')
print()
_board=[[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,1,1,0,0,0],
[0,0,0,1,1,0,1,1,0,0],
[0,0,1,1,0,0,0,0,1,0],
[0,0,1,0,0,0,0,0,1,0],
[0,1,0,0,0,0,0,1,0,0],
[0,0,1,0,0,0,0,1,0,0],
[0,0,0,1,1,0,0,1,0,0],
[0,0,0,0,0,1,1,0,0,0],
[0,0,0,0,0,0,0,0,0,0]]
def drawColor(row,col,color,tboard):
if row<0 or col<0:
return
elif tboard[col][row] != 0:
#이미 색이 칠해진 공간은 패스하기 위해 0이 아닌 조건으로 설정.
return
else:
tboard[col][row] = color
drawColor(row-1,col,color,tboard)
drawColor(row+1,col,color,tboard)
drawColor(row,col-1,color,tboard)
drawColor(row,col+1,color,tboard)
drawColor(5,5,3,_board)
for i in _board:
print(i)
width, height = map(int, input().split())
px, py, color = map(int, input().split())
l = [None]
for y in range(1, height+1):
s = input()
l.append([None])
for i in s:
l[y].append(i)
def inRange(x, y):
global width, height
return 1<=x<=width and 1<=y<=height
def dfs(x, y):
global l, color
if inRange(x, y) and l[y][x] == '0':
l[y][x] = str(color)
dfs(x+1, y)
dfs(x-1, y)
dfs(x, y+1)
dfs(x, y-1)
dfs(px, py)
for y in range(1, height+1):
for x in range(1, width+1):
print(end=l[y][x])
print()
Python3입니다. DFS로 색을 채웠습니다.
/* INPUT 10 10 5 5 3 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
OUTPUT 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 3 1 0 0 0 0 1 1 3 3 3 3 1 0 0 1 3 3 3 3 3 3 1 0 0 1 3 3 3 3 3 3 1 0 0 1 3 3 3 3 3 1 0 0 0 0 1 3 3 3 1 0 0 0 0 0 0 1 3 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 */ import java.util.Scanner;
public class sol089 {
static int x;
static int y;
static int box[][];
public static void paint(int cur_x, int cur_y, int color) {
box[cur_x][cur_y] = color;
if(cur_x < box.length-1 && box[cur_x+1][cur_y] == 0) paint(cur_x+1, cur_y, color);
if(cur_x > 0 && box[cur_x-1][cur_y] == 0) paint(cur_x-1, cur_y, color);
if(cur_y < box.length-1 && box[cur_x][cur_y+1] == 0) paint(cur_x, cur_y+1, color);
if(cur_y > 0 && box[cur_x][cur_y-1] == 0) paint(cur_x, cur_y-1, color);
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
x = sc.nextInt();
y = sc.nextInt();
box = new int[x][y];
int st_x = sc.nextInt();
int st_y = sc.nextInt();
int color = sc.nextInt();
for(int i=0; i<box.length; i++) {
for(int j=0; j<box[i].length; j++) {
box[i][j] = sc.nextInt();
}
}
paint(st_x, st_y, color);
for(int i=0; i<box.length; i++) {
for(int j=0; j<box[i].length; j++) {
System.out.print(box[i][j] + " ");
}
System.out.println();
}
}
}
from copy import deepcopy
r_data = '''0000000000
0000001000
0000110100
0011000010
0100000011
0100000000
0100000111
0010001000
0001011000
0000100000'''
data = [list(i) for i in r_data.split()]
class painter :
def BFS(self, map_, x, y) :
queue = [[x, y]]
dx_dy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while len(queue) != 0 :
pop_data = deepcopy(queue.pop(0))
for cond in dx_dy :
copy_data = deepcopy(pop_data)
try :
if (map_[copy_data[1]+cond[1]][copy_data[0]+cond[0]]) == '0' :
map_[copy_data[1]+cond[1]][copy_data[0]+cond[0]] = '3'
queue.append([copy_data[0]+cond[0], copy_data[1]+cond[1]])
except :
pass
return self.printOut(map_)
def printOut(self, map__) :
for line in map__ :
print("".join(line))
if __name__ == '__main__' :
a = painter()
a.BFS(data, 5, 5)
BFS로 풀었고 좌표가 배열의 범위를 벗어나는 경우에 대해서는 예외처리했습니다. 배워도 배워도 끝이 없네요~
결과
0000000000
0000001000
0000113100
0011333310
0133333311
0133333333
0133333111
0013331000
0001311000
0000100000
canvas="""0000000000
0000001000
0000110100
0011000010
0100000010
0100000010
0100000100
0010001000
0001011000
0000100000"""
lst=[list(ln) for ln in canvas.split("\n")]
maxX,maxY=len(lst[0]),len(lst)
def solve(y,x,fill):
if lst[y][x]=="0" and lst[y][x]!="1":
lst[y][x]=str(fill)
for dx, dy in [(1,0),(0,1),(-1,0),(0,-1)]:
nx,ny=x+dx,y+dy
if 0<=nx<maxX and 0<=ny<maxY and lst[ny][nx]=="1":
continue
elif 0<=nx<maxX and 0<=ny<maxY and lst[ny][nx]=="0":
lst[ny][nx]=str(fill)
solve(ny,nx,fill)
return lst
solve(5,5,3)
for ln in lst:
for cmp in ln:
print("%1s"%cmp, end="")
print()
결과
0000000000
0000001000
0000113100
0011333310
0133333310
0133333310
0133333100
0013331000
0001311000
0000100000
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]]
def bfs(r,c):
global map_, color, width, height
for (dr,dc) in ((1,0),(0,1),(-1,0),(0,-1)):
y, x = r+dr, c+dc
if 0<=y<height and 0<=x<width and map_[y][x] == 0:
map_[y][x] = color
bfs(y, x)
bfs(row, col)
for r in range(width):
for c in range(height):
print(map_[r][c], end=" ")
print()